dorsal/arxiv
View SchemaReconfiguration of Hamiltonian Paths and Cycles in Rectangular Grid Graphs
| Authors | Albi Kazazi |
|---|---|
| Categories | |
| ArXiv ID | 2601.06749vv1 |
| URL | https://arxiv.org/abs/2601.06749 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
\noindent An \textit{\(m \times n\) grid graph} is the induced subgraph of the square lattice whose vertex set consists of all integer grid points \(\{(i,j) : 0 \leq i < m,\ 0 \leq 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 \textit{moves}. A \textit{box} of $G$ is a unit square face. A box with vertices $a, b, c, d$ is \textit{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 \textit{switch move} removes $ab$ and $cd$, and adds $bc$ and $ad$. A \textit{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 \textit{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 \textit{backbite move}, which enables the relocation of the path endpoints.
{
"annotation_id": "a017b4e7-8de2-4b22-8b8e-5c4e636e6fe6",
"date_created": "2026-02-17T05:53:07.826000Z",
"date_modified": "2026-02-17T05:53:07.826000Z",
"file_hash": "b222dacf1ff6d5795b13d7956a211fe4b0710b5469fc4fca7493f74efed7b227",
"private": false,
"record": {
"abstract": "\\noindent An \\textit{\\(m \\times n\\) grid graph} is the induced subgraph of the square lattice whose vertex set consists of all integer grid points \\(\\{(i,j) : 0 \\leq i \u003c m,\\ 0 \\leq j \u003c 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 \\textit{moves}. A \\textit{box} of $G$ is a unit square face. A box with vertices $a, b, c, d$ is \\textit{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 \\textit{switch move} removes $ab$ and $cd$, and adds $bc$ and $ad$. A \\textit{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 \\textit{valid}.\n 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.\n This result extends to Hamiltonian paths. In that case, we also use single-switch moves and a third operation, the \\textit{backbite move}, which enables the relocation of the path endpoints.",
"arxiv_id": "2601.06749",
"authors": [
"Albi Kazazi"
],
"categories": [
"math.CO"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Reconfiguration of Hamiltonian Paths and Cycles in Rectangular Grid Graphs",
"url": "https://arxiv.org/abs/2601.06749",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "53000483-40e9-40b6-9e6d-11c5825717ae",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}