4
$\begingroup$

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

  • 0
    @Brian That certainly is simpler. Thanks.2011-08-22

1 Answers 1

1

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

  • 0
    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.2011-09-22