dorsal/arxiv
View SchemaReconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
| Authors | Albi Kazazi |
|---|---|
| Categories | |
| ArXiv ID | 2601.06731vv1 |
| URL | https://arxiv.org/abs/2601.06731 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
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$, \textcolor{blue}{\textbullet} where the Hamiltonian cycles are viewed as vertices of a reconfiguration graph \textcolor{blue}{\textbullet}, 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. Moreover, assuming $n \geq m$, the number of required moves is bounded by $mn^2$.
{
"annotation_id": "636fa7b3-df51-43a0-a1ee-fa1837edd17a",
"date_created": "2026-02-17T05:53:08.097000Z",
"date_modified": "2026-02-17T05:53:08.097000Z",
"file_hash": "d8ab3b22c2f830ac201f1c5aec287d32a12f219dda45af1d51e3e199e812d2fd",
"private": false,
"record": {
"abstract": "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$, \\textcolor{blue}{\\textbullet} where the Hamiltonian cycles are viewed as vertices of a reconfiguration graph \\textcolor{blue}{\\textbullet}, 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. Moreover, assuming $n \\geq m$, the number of required moves is bounded by $mn^2$.",
"arxiv_id": "2601.06731",
"authors": [
"Albi Kazazi"
],
"categories": [
"math.CO"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs",
"url": "https://arxiv.org/abs/2601.06731",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f270841a-c995-4228-b09e-aa37fcc0c190",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}