# Upper bound for the number of hamilton cycles in a cubic graph

Wikipedia states, that it has been proven, that there are at most $1.276^n$ hamilton cycles in a cubic graph with $n$ nodes. This upper bound is not valid for $n=6$. The values I found out using an online calculator are $(H(n)$ is the true maximum number of hamilton-cycles) :

$$n\ \ \ \ \ \ \ \ ceil(1.276^n) \ \ \ \ \ \ \ H(n)$$

$$4\ \ \ \ \ \ \ \ \ 3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3$$ $$6\ \ \ \ \ \ \ \ \ 5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6$$ $$8\ \ \ \ \ \ \ \ \ 8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6$$ $$10\ \ \ \ \ \ \ \ \ 12\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 12$$ $$12\ \ \ \ \ \ \ \ \ 19\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 16$$ $$14\ \ \ \ \ \ \ \ \ 31\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 24$$ $$16\ \ \ \ \ \ \ \ \ 50\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 32$$ $$18\ \ \ \ \ \ \ \ \ 81\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 64$$

My questions :

• Are my values for $H(n)$ correct ?
• Is the upper bound valid for $n>6$ ? (I could not open the link wikipedia shows)
• Upto which $n$ is the true value $H(n)$ known ?
• Is the upper bound asymptotically sharp; does $$\lim_{n->\infty} \frac{1.276^n}{H(n)}=1$$ hold ?
• I used the ceil-function (rounding up). If I would use the truncate-function, only the values for $n\ge 12$ (and for $n=8$) would be valid. – Peter Oct 27 '14 at 17:25

• I get the same values for $H(n)$
• The bound in the paper is an asymptotical bound, that is the number of Hamiltonian cycles in a cubic graph is $O({1.276}^n).$
• I don't think $H(n) \sim {1.276}^n.$ If this were known, the authors would state the result involving $\Theta$ not $O$
• So, $H(n)<=1.276^n$ need not be true for all $n>6$ ? (Since the bound is only asymptotical) – Peter Oct 27 '14 at 17:53
• Exactly. What you do know though is that the limit you mention is $\leq c$ for some $c > 0.$ – Jernej Oct 27 '14 at 17:54
• @Peter I forgot to mention that in this context $c$ can as well be infinity. – Jernej Oct 28 '14 at 8:38