# Complexity of Hamiltonian Cycle Reconfiguration
## 3 Canonical Hamiltonian Cycles
### Unit Interval Graphs  
A graph is an _interval graph_ if each vertex can be assigned an interval on the real line so that two vertices are adjacent if and only if their assigned intervals intersect. An interval graph is a _unit interval graph_ if each vertex can be assigned an interval of unit length. There are some linear-time algorithms to find a Hamiltonian cycle of a unit interval graph [14; 15; 16]. We follow the algorithm of [PERSON] et al. [14], which uses the following vertex ordering characterization. Theorem 3.1 ([14; 22]): _A consecutive ordering of a graph \(G\) is a sequence of vertices \(v_{0},v_{1},\ldots,v_{n-1}\) of \(G\) such that for any three vertices \(v_{i},v_{j},v_{k}\) with \(i<j<k\), if \(v_{i}v_{k}\in E(G)\) then \(v_{i}v_{j},v_{j}v_{k}\in E(G)\). A graph is a unit interval graph if and only if it has a consecutive ordering. Moreover, a consecutive ordering of a unit interval graph can be obtained in linear time._  
Notice that, in the consecutive ordering of a graph \(G\), the vertices in \(N[v]\) are consecutive for every vertex \(v\in V(G)\), where \(N[v]=\{v\}\cup\{u:\ uv\in E(G)\}\). It is known that a unit interval graph has a Hamiltonian cycle if and only if it is biconnected [14; 15; 16]. Biconnected unit interval graphs are characterized as follows. **Theorem 5** ([14]). : _A unit interval graph \(G\) with a consecutive ordering \(v_{0},v_{1},\ldots,v_{n-1}\) is biconnected if and only if \(v_{i}v_{j}\in E(G)\) for every \(i\) and \(j\) with \(1\leq|i-j|\leq 2\)._  
We can observe that such a unit interval graph \(G\) has a Hamiltonian cycle consisting of the edges \(v_{0}v_{1}\), \(v_{n-2}v_{n-1}\), and \(v_{i}v_{i+2}\) for every \(i\) with \(0\leq i\leq n-3\)[14]; we define it as the _canonical Hamiltonian cycle_ (_canonical cycle_ for short) of \(G\). **Theorem 6**. : _Let \(G\) be a unit interval graph. For each Hamiltonian cycle of \(G\), there is a sequence of at most \(n-2\) switches transforming it to the canonical cycle of \(G\)._  
The following is a useful fact about consecutive orderings. **Lemma 3**. : _Let \(v_{i},v_{j},v_{k},v_{h}\) be four vertices of \(G\) with \(i<j<k\) and \(i<h\). If \(v_{i}v_{k},v_{j}v_{h}\in E(G)\), then \(v_{i}v_{j},v_{k}v_{h}\in E(G)\)._  
Proof. : We have that \(v_{i}v_{k}\) implies \(v_{i}v_{j}\in E(G)\) by the definition of consecutive orderings. If \(h<k\), then \(v_{i}v_{k}\in E(G)\) and \(i<h\) implies \(v_{k}v_{h}\in E(G)\). If \(k<h\), then \(v_{j}v_{h}\in E(G)\) implies \(v_{k}v_{h}\in E(G)\). Proof of Theorem 6.: We assume \(n\geq 4\), since the claim trivially holds when \(n\leq 3\). Let \(G\) have a consecutive ordering \(v_{0},v_{1},\ldots,v_{n-1}\), and let \(C_{t}\) be the canonical cycle of \(G\). Let \(C_{0}\) be a Hamiltonian cycle of \(G\). It suffices to show a sequence of Hamiltonian cycles \(C_{0},C_{1},\ldots,C_{n-2}\) that satisfy the following conditions for each \(i\) with \(1\leq i\leq n-2\):  
* \(C_{i}\) contains the edges on \(C_{t}\) induced by \(\{v_{0},v_{1},\ldots,v_{i}\}\),
* \(C_{i}\) is obtained from \(C_{i-1}\) by _at most one_ switch. Notice that \(C_{n-2}\) is the canonical cycle \(C_{t}\) by the following reason: since \(C_{n-2}\) is Hamiltonian, \(v_{n-3}v_{n-2}\
otin E(C_{n-2})\); we thus have \(v_{n-3}v_{n-1},v_{n-2}v_{n-1}\in E(C_{n-2})\). We first construct \(C_{1}\) from \(C_{0}\). When \(v_{0}v_{1}\in E(C_{0})\), we define \(C_{0}\) as \(C_{1}\). We then consider the case when \(v_{0}v_{1}\
otin E(C_{0})\). Let \(v_{j},v_{k},v_{h},v_{l}\) be the vertices of \(G\) such that  
\[C_{0}=(v_{0},v_{j},\ldots,v_{k},v_{1},v_{h},\ldots,v_{l}).\]  
Note that there is some possibility that \(v_{j}=v_{k}\) or \(v_{h}=v_{l}\). It is clear that \(j,k,h,l\geq 2\). Since \(v_{0}v_{j},v_{1}v_{h}\in E(G)\), we have \(v_{0}v_{1},v_{j}v_{h}\in E(G)\) by Lemma 3.