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.

$\endgroup$
  • $\begingroup$ Careful – one of the reasons for closing questions is that they are "primarily opinion-based". $\endgroup$ – Gerry Myerson May 23 '17 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 May 23 '17 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 May 23 '17 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 May 24 '17 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 May 24 '17 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.