I am currently interested in hamilton cycles (i.e. a cycle through every vertex) in planar triangulations (i.e. planar graphs with every face a triangle).

There are non-hamiltonian planar triangulations about which I have nothing to say or ask. However if a planar triangulation is hamiltonian then it has at least 4 hamilton cycles, and Hakimi, Schmeichel and Thomassen (HST) found an infinite family of planar triangulations with exactly 4 hamilton cycles. However the only infinite families of planar triangulations with a bounded number of hamilton cycles have separating triangles (i.e. 3-vertex clique-cutsets) and can in some sense be viewed as "reducible'' configurations.

Therefore HST asked what is the smallest number of hamilton cycles that a $4$-connected planar triangulation on $n$ vertices can have, and conjectured that the answer is $2(n-2)(n-4)$ hamilton cycles. Furthermore they conjectured that the unique example realising this is the complete join of $2K_1$ (two isolated vertices) to a cycle of length $n-2$.

My question is whether this has been proved or any progress has been made on it. I have searched fairly hard through MathSciNet and Google, and have convinced myself that there are no small counterexamples.

  • $\begingroup$ True up to 16 vertices... $\endgroup$ – Brendan McKay Feb 19 '17 at 9:13
  • $\begingroup$ @Brendan - I've done all I could do with plantri in an afternoon... it looks very solid, but can't think of how to play prove! $\endgroup$ – Gordon Royle Feb 19 '17 at 9:57
  • $\begingroup$ Can you provide a link to HST paper? $\endgroup$ – Ilya Bogdanov Apr 14 '17 at 14:50
  • $\begingroup$ Ilya, the paper is here: dx.doi.org/10.1002/jgt.3190030407. (However for me it is behind a paywall, and I had to actually physically walk to our library to look at it.) $\endgroup$ – Gordon Royle Apr 15 '17 at 0:46

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.