Max-turn hamiltonian path in square grids

Question

Given an $n \times n$ square grid graph, what is the maximum number of turns a Hamiltonian path can take?

Answer 1

Answer to OP's question (proof follows):

For Hamitlonian paths: if $n$ is even max turns=$n^2-n$

if $n$ is odd max turns equals $n^2-n-1$

The minimum number of turns on an Hamiltonian path on an $n \times n$ lattice is $2n-2$ which can be constructed at least two non-isomorphic ways (rows or spiral) for each graph. The maximum number of turns Hamiltonian path onin a $2 \times n$ lattice is also $2n-2$

To maximize the number of turns, if $n$ is even then you can consider the graph to be a collection of $n \times 2$ graphs each of which can have a maximum of $2n-2$ turns in them starting from an outside corner on each side the $-2$ factor comes from the fact that in order to turn the corner you must have one vertex that does not turn, for an outside $2 \times n$ you lose one going into the corner and one from the starting/ending vertex. For the interior $2 \times n$'s you must have one "straight vertex coming in and one coming out.

$2n-2 \times (n/2)$seperate rectangles gives a formula of $n^2-n$ for even $n$.

If $n$ is odd, it is not so simple to construct a path because the rows do not divide evenly by $2$. The cases for constrcution of a maximal turning path are different if $n$ is 1 or 3 mod $4$.

If $n=1$ mod $4$ you begin again at a corner in the first row you again have $2n-2$ turning vertices in the first $2\times n$ rectangle. You then continue down the side of the graph (a $2\times (n-2)$ rectangle) and collect $2n-4-1$ more turning vertices. Repeat on the bottom of the graph. Continue towards the starting corner now you have a $2 \times (n-4)$ rectangle that yields $2n-8-1$ turning vertices. Continue on towards the center every two new directions you turn the rectangle get smaller and there are $4$ fewer vertices. When you reach the center (where the path ends) you gain only 1 turn for the final $3$ vertices.

Putting it all together there are $n-2$ turns in the first rectangle, $1$ turn for the center and the spiral which contains $n-7+4$ rectangles in sets of two beginning with $2n-5$ turns and adding $4$ less for every set. $2n-2+1+[(n-3)(\frac{2n+5-5}{2})]=n^2-n-1$

If $n=3$ mod $4$ then you can proceed as above but the actual center vertex of the graph is contained in the last rectangle before the end of the paththe last $3$ vertices and their $1$ turn remains the same but the path is off-centered in the graph. The formula for the vertices remains the same $2n-2$ for the first rectangle $n-5$ rectangles at an average of $n$ turns per spiral rectangle and one for the last turn of the path still sums to $n^2-n-1$ for all odd $n$.

Answer to question asked in comments. For Hamiltonian Cycles

If $n$ is odd there is no hamiltonian cycle on a $n \times n$ grid. This can be proved from the contrapositive of theorem 3.16 on page 214 of "Graphs and Digraphs" by Chartrand. By numbering the vertices of an odd $n \times n$ grid from left to right top to bottom from $1,2,3...n^2$ Select the set of vertices $S$ as all the even numbered vertices. Then $|S|=\frac{n^2-1}{2}$ and there are $\frac{n^2+1}{2}$ disconnected components so the graph cannot be hamiltonian.

If $n$ is even you can construct a "spiral" cycle like the spirals for the odd paths given above. I haven't found a closed form expression yet that deals with the center of the cycle. $(\frac{3n^2}{4}+\frac{3n}{2}-12)+C$ where $C$ is the number of turns at the center of the graph is a good description of the maximum number of turns in a hamiltonian cycle on a $n \times n$ grid.