# Complexity of Hamiltonian Cycle Reconfiguration
## 3 Canonical Hamiltonian Cycles
### Unit Interval Graphs
We define that \(C_{1}\) is the Hamiltonian cycle obtained from \(C_{0}\) by switching the edges \(v_{0}v_{j}\) and \(v_{1}v_{h}\) with the edges \(v_{0}v_{1}\) and \(v_{j}v_{h}\), that is,  
\[C_{1}=(v_{0},v_{1},v_{k},\ldots,v_{j},v_{h},\ldots,v_{l}).\]  
We now construct \(C_{i}\) from \(C_{i-1}\) with \(i\geq 2\). Recall that \(C_{i-1}\) contains the edges on \(C_{t}\) induced by \(\{v_{0},\ldots,v_{i-2},v_{i-1}\}\). When \(v_{i-2}v_{i}\in E(C_{i-1})\), we define \(C_{i-1}\) as \(C_{i}\). We then consider the case when \(v_{i-2}v_{i}\
otin E(C_{i-1})\). Let \(v_{j},v_{k},v_{h}\) be the vertices of \(G\) such that  
\[C_{i-1}=(v_{i-1},\ldots,v_{i-2},v_{j},\ldots,v_{k},v_{i},v_{h},\ldots).\]Note that there is some possibility that \(v_{j}=v_{k}\) or \(v_{i-1}=v_{h}\). We have \(j>i-2\) by the definition of \(C_{i-1}\). Since \(C_{i-1}\) is Hamiltonian, \(v_{i-2}v_{i-1}\
otin E(C_{i-1})\), and thus \(j\
eq i-1\). We also have \(j>i\) from \(v_{i-2}v_{i}\
otin E(C_{i-1})\). Moreover, we have \(k,h>i-2\) by the definition of \(C_{i-1}\) and \(v_{i-2}v_{i}\
otin E(C_{i-1})\). Since \(v_{i-2}v_{j},v_{i}v_{h}\in E(G)\), we have \(v_{i-2}v_{i},v_{j}v_{h}\in E(G)\) by Lemma 3. We define that \(C_{i}\) is the Hamiltonian cycle obtained from \(C_{i-1}\) by switching the edges \(v_{i-2}v_{j}\) and \(v_{i}v_{h}\) with the edges \(v_{i-2}v_{i}\) and \(v_{j}v_{h}\), that is,  
\[C_{i}=(v_{i-1},\ldots,v_{i-2},v_{i},v_{k},\ldots,v_{j},v_{h},\ldots).\]  
Therefore, we have the sequence of at most \(n-2\) switches transforming \(C_{0}\) into the canonical cycle \(C_{t}\). We also have the following from Theorem 6. Corollary 1: _For each Hamiltonian cycle \(C_{0}\) of a unit interval graph \(G\), we can compute a sequence of switches transforming \(C_{0}\) to the canonical cycle of \(G\) in \(O(n)\) time, provided that a consecutive ordering of \(G\) is given._  
Proof: The algorithm follows the steps of the proof of Theorem 6. We analyze the implementation details and the running time. We store \(C_{0}\) in a circular doubly linked list \(L\) as a sequence of vertices; we store the consecutive ordering \(v_{0},v_{1},\ldots,v_{n-1}\) in an array \(A\), in which the element of position \(i\) has a pointer to the vertex \(v_{i}\) in \(L\) for each \(i\) with \(0\leq i<n\). In order to compute the Hamiltonian cycle \(C_{1}\) from \(C_{0}\), it suffices to take the vertices \(v_{0},v_{1},v_{j},v_{h}\) in \(L\), where \(v_{j}\) and \(v_{h}\) is the successor or the predecessor of \(v_{0}\) and \(v_{1}\), respectively. Similarly in order to compute \(C_{i}\) from \(C_{i-1}\) with \(i\geq 2\), it suffices to take the vertices \(v_{i-2},v_{i},v_{j},v_{h}\) in \(L\), where \(v_{j}\) and \(v_{h}\) is the successor or the predecessor of \(v_{i-2}\) and \(v_{i}\), respectively. Since one iteration takes a constant time, we have the claim. Now, we have the following from Theorem 6 and Corollary 1. Corollary 2: _For any two Hamiltonian cycles of a unit interval graph, there is a sequence of at most \(2n-4\) switches transforming one cycle to the other. Moreover, we can compute such a sequence in \(O(n)\) time, provided that a consecutive ordering of \(G\) is given._