Connectivity of the reconfiguration graph of Hamiltonian paths

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 $\delta (G)\ge \lceil \frac{2n-1}{3}\rceil$, for the circulants $\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}(n;S)$ with $a,2a\in S$ for some $a$ coprime to $n$, and, with high probability, for the random graph $G(n,p)$ with $p\ge c\mathrm{/}\sqrt{n}$, for a sufficiently large constant $c$. In the other direction, graphs with arbitrarily high connectivity may have disconnected reconfiguration graphs. For every $n\ge 8$ and every $1\le m\le \lfloor n\mathrm{/}2\rfloor -3$ we construct a graph on $n$ vertices with $\kappa =\lambda =\delta =m$ whose reconfiguration graph is disconnected, with at least $(n-2m-4)!$ components. We conjecture that $\delta (G)\ge n\mathrm{/}2$ suffices for connectivity.