1
$\begingroup$

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 ?
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter Oct 27 '14 at 17:25
2
$\begingroup$
  • 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$

The mentioned paper can be found here.

$\endgroup$
  • $\begingroup$ So, $H(n)<=1.276^n$ need not be true for all $n>6$ ? (Since the bound is only asymptotical) $\endgroup$ – Peter Oct 27 '14 at 17:53
  • 1
    $\begingroup$ Exactly. What you do know though is that the limit you mention is $\leq c$ for some $c > 0.$ $\endgroup$ – Jernej Oct 27 '14 at 17:54
  • $\begingroup$ @Peter I forgot to mention that in this context $c$ can as well be infinity. $\endgroup$ – Jernej Oct 28 '14 at 8:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.