5
$\begingroup$

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph?

I did some searching and found that the number of hamiltonian cycles on a planar graph with $n$ vertices is $O(\sqrt[4]{30}^n)$ where $n$ is the number of vertices in the graph. For grid graphs, I just found enumerations for small $n$, but no bounds.

$\endgroup$

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.