Connectivity of the reconfiguration graph of Hamiltonian paths
Abstract
A backbite on a Hamiltonian path of a graph G adds an edge of G from an endpoint u of the path to a vertex v and deletes an edge of the path at v so that the result is again a Hamiltonian path. We study the connectivity of the reconfiguration graph R(G), whose vertices are the Hamiltonian paths of G, with two adjacent when a single backbite carries one to the other. We prove that R(G) is connected whenever G contains the square of a Hamiltonian path as a spanning subgraph, and that any two Hamiltonian paths can be reconfigured using O(n2) backbites. Combining the theorem with known results on spanning squared paths gives connectivity for every graph with δ(G)≥⌈(2n−1)/3⌉, for the circulants Circ(n;S) with a,2a∈ S for some a coprime to n, and, with high probability, for the random graph G(n,p) with p≥ c/√n, for a sufficiently large constant c. In the other direction, graphs with arbitrarily high connectivity may have disconnected reconfiguration graphs. For every n≥8 and every 1≤ m≤⌊ n/2⌋−3 we construct a graph on n vertices with κ=λ=δ=m whose reconfiguration graph is disconnected, with at least $(n-2m-4)!$ components. We conjecture that δ(G)≥ n/2 suffices for connectivity.
Related
- Rainbow Hamiltonian paths in graph collections under edge-size conditions
- Enumerating Hamiltonian Paths and Cycles
- Arc-disjoint Hamiltonian paths in Cayley digraphs with a normal difference subgroup
- Strongly separating graph edges with 10n paths
- Connectivity keeping pendant extensions of paths in k-connected graphs and triangle-free graphs
BibTeX
@misc{kazazi2026connectivity,
title = {{Connectivity of the reconfiguration graph of Hamiltonian paths}},
author = {Albi Kazazi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05068},
eprint = {2610.05068},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05068},
}
RIS
TY - UNPB
TI - Connectivity of the reconfiguration graph of Hamiltonian paths
AU - Albi Kazazi
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05068
UR - https://arxiv.org/abs/2610.05068
AB - A backbite on a Hamiltonian path of a graph G adds an edge of G from an endpoint u of the path to a vertex v and deletes an edge of the path at v so that the result is again a Hamiltonian path. We study the connectivity of the reconfiguration graph R(G), whose vertices are the Hamiltonian paths of G, with two adjacent when a single backbite carries one to the other. We prove that R(G) is connected whenever G contains the square of a Hamiltonian path as a spanning subgraph, and that any two Hamiltonian paths can be reconfigured using O(n^2) backbites. Combining the theorem with known results on spanning squared paths gives connectivity for every graph with δ(G)≥⌈(2n−1)/3⌉, for the circulants Circ(n;S) with a,2a∈ S for some a coprime to n, and, with high probability, for the random graph G(n,p) with p≥ c/√n, for a sufficiently large constant c. In the other direction, graphs with arbitrarily high connectivity may have disconnected reconfiguration graphs. For every n≥8 and every 1≤ m≤⌊ n/2⌋−3 we construct a graph on n vertices with κ=λ=δ=m whose reconfiguration graph is disconnected, with at least $(n-2m-4)!$ components. We conjecture that δ(G)≥ n/2 suffices for connectivity.
ER -