Reconfiguration of Hamiltonian Paths and Cycles in Rectangular Grid Graphs

\noindent An $m\times n\mathit{\text{grid}}\mathit{\text{graph}}$ is the induced subgraph of the square lattice whose vertex set consists of all integer grid points $\{(i,j):0\le i<m,0\le j<n\}$. Let $H$ and $K$ be Hamiltonian cycles in an $m\times n$ grid graph $G$. We study the problem of reconfiguring $H$ into $K$ using a sequence of local transformations called $\mathit{\text{moves}}$. A $\mathit{\text{box}}$ of $G$ is a unit square face. A box with vertices $a,b,c,d$ is $\mathit{\text{switchable}}$ in $H$ if exactly two of its edges belong to $H$, and these edges are parallel. Given such a box with edges $ab$ and $cd$ in $H$, a $\mathit{\text{switch}}\mathit{\text{move}}$ removes $ab$ and $cd$, and adds $bc$ and $ad$. A $\mathit{\text{double-switch}}\mathit{\text{move}}$ consists of performing two consecutive switch moves. If, after a double-switch move, we obtain a Hamiltonian cycle, we say that the double-switch move is $\mathit{\text{valid}}$. We prove that any Hamiltonian cycle $H$ can be transformed into any other Hamiltonian cycle $K$ via a sequence of valid double-switch moves, such that every intermediate graph remains a Hamiltonian cycle. This result extends to Hamiltonian paths. In that case, we also use single-switch moves and a third operation, the $\mathit{\text{backbite}}\mathit{\text{move}}$, which enables the relocation of the path endpoints.