Reconfiguration of Hamiltonian Cycles and Paths in Rectangular Grid Graphs

Abstract

An m×n grid graph is the induced subgraph of the square lattice whose vertex set consists of all integer grid points {(i, j) : 0 ≤ i < m, 0 ≤ j < n}. Let H and K be Hamiltonian cycles in an m × n grid graph G. We study the problem of reconfiguring H into K using a sequence of local transformations called moves. A box of G is a unit square face. A box with vertices a, b, c, d is 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 switch move removes ab and cd, and adds bc and ad. A double-switch 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 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 backbite move, which enables the relocation of the path endpoints.