Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
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. –  Brian M. Scott Aug 22 '11 at 1:58
    
@Brian That certainly is simpler. Thanks. –  user12998 Aug 22 '11 at 1:59

1 Answer 1

up vote 1 down vote accepted
+250

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

share|improve this answer
1  
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. –  user12998 Sep 21 '11 at 22:57
    
Perhaps you could post your solution as an answer. –  David Bevan Sep 22 '11 at 8:06
    
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. –  user12998 Sep 22 '11 at 15:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.