This question comes from a comment on this older question about the maximum number of turns in a Hamiltonian path, on an $n \times n$ lattice. @Joseph Malkevitch asked if the results could be extended to Hamiltonian cycles.

If $n$ is odd then you cannot construct a Hamiltonian cycle on an $n \times n$ graph. This can be demonstrated by labeling the vertices from left to right and top to bottom, on an odd $n \times n$ lattice from $1,2,3…n^2$. Select the set of even numbered vertices, $S$. Then, $\kappa (G-s)= \frac{n^2+1}{2}\gt |S|=\frac{n^2-1}{2}$ which disproves the existence of a Hamiltonian cycle.

If $n=0$ mod$4$ then you can exploit the symmetry of the maximal Hamiltonian cycle to show that the maximum number of turns possible in a Hamiltonian cycle is $n^2-n$

I haven’t been able to make much progress in the case where $n=2$ mod $4$, either in terms of creating a constructive algorithm or identifying a likely polynomial in terms of $n$.

Actual Question. What is the maximum number of turns in a Hamiltonian cycle on an $n \times n$ lattice graph with $n=2$ mod $4$?

  • $\begingroup$ The non-existence in case $n$ is odd can be shown even more simply: just color the vertices alternately red and blue, and note that a Hamilton circuit must then have an odd number of vertices of alternating colors $-$ which is a wee bit difficult. $\endgroup$ – Brian M. Scott Aug 22 '11 at 1:58
  • $\begingroup$ @Brian That certainly is simpler. Thanks. $\endgroup$ – user12998 Aug 22 '11 at 1:59

For $n\equiv 10 \pmod{12}$, the maximum number of turns is at least $n^2-2n+4$. Here are diagrams for $n=10$ and $n=22$:

$\hskip 0.5 in$ Hamiltonian cycle on a 10×10 lattice graph $\hskip 0.5 in$ Hamiltonian cycle on a 22×22 lattice graph

  • 1
    $\begingroup$ Those pictures are great. After posting the bounty I finally found a closed form solution that seems to work for all cases, I get the same result for $n=10$ but I think you can get add 8 more turns to the $n=22$ case. Thanks. $\endgroup$ – user12998 Sep 21 '11 at 22:57
  • $\begingroup$ Perhaps you could post your solution as an answer. $\endgroup$ – David Bevan Sep 22 '11 at 8:06
  • $\begingroup$ Since I offered the bounty, it has to go to someone else's answer. I would prefer to award it to someone, so I will wait until the bounty ends before posting my answer. $\endgroup$ – user12998 Sep 22 '11 at 15:34

Your Answer

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