9
$\begingroup$

Sheehan conjectured that there are no 4-regular graphs that are uniquely hamiltonian (i.e. have exactly one hamilton cycle).

Evidence that might be loosely seen to be in favour of this conjecture is: that even 3-regular graphs cannot be uniquely hamiltonian, that regular graphs of high enough valency cannot be uniquely hamiltonian, and that it seems (empirically) difficult to make uniquely hamiltonian graphs that do not have most of their vertices of degree 3.

However all of this seems rather inconsequential compared to Fleischner's examples of uniquely hamiltonian graphs of minimum degree 4, which are biregular with degrees 4 and 14. This suggests that provided you've got enough vertices and enough edges, you can connect up cycle-forcing and cycle-avoiding "gadgets" in various complicated ways to ultimately enforce unique hamiltonicity.

At the moment, I'm leaning towards the position that the conjecture is most likely false, but that the smallest counterexample will have hundreds or thousands of vertices.

I'd be interested in hearing other heuristic arguments in either direction, maybe the poster's own informed opinion (see comments) or one that they have read in the literature, or one that they have heard in seminars etc.

Improve this question
$\endgroup$
5
  • $\begingroup$ Careful – one of the reasons for closing questions is that they are "primarily opinion-based". $\endgroup$
    – Gerry Myerson
    Commented May 23, 2017 at 12:13
  • $\begingroup$ Yes, I tried to indicate "informed opinion" or "heuristic argument" to emphasise that I'm not after unsupported guesses, and to distinguish this from questions that have no mathematical answer and hence really are just opinion ("was Bourbaki good or bad for mathematics?") $\endgroup$
    – Gordon Royle
    Commented May 23, 2017 at 12:59
  • $\begingroup$ Are there some obvious properties that a counterexample must have? I'm guessing edge and vertex transitivity must fail, and there might be restrictions on the shape of a two- or three-Hop neighborhood of any vertex. Gerhard "Just Guessing About Graph Jumps" Paseman, 2017.05.23. $\endgroup$
    – Gerhard Paseman
    Commented May 23, 2017 at 17:56
  • $\begingroup$ @Gerhard I don't think anything really is known about a minimum counterexample; the problem doesn't really seem to lend itself to inductive arguments because the interaction between hamilton cycles and inductive constructions for regular graphs seems impossible to handle. For example, Barnette's conjecture would be solved if only we could keep track of hamilton cycles through a couple of "moves" used in building larger cubic graphs from smaller ones. $\endgroup$
    – Gordon Royle
    Commented May 24, 2017 at 5:11
  • $\begingroup$ @Gerhard of course a counter example cannot be edge-transitive because then every edge is in the same number of Hamilton cycles... $\endgroup$
    – Gordon Royle
    Commented May 24, 2017 at 9:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .