# Complexity of Hamiltonian Cycle Reconfiguration
## 3 Canonical Hamiltonian Cycles
### Bipartite Permutation Graphs  
A graph \(G\) with the vertex set \(V(G)=\{v_{1},v_{2},\ldots,v_{n}\}\) is a _permutation graph_ if there is a permutation \(\pi\) on \(\{1,2,\ldots,n\}\) such that \(v_{i}v_{j}\in E(G)\) if and only if \((i-j)(\pi(i)-\pi(j))<0\) for every \(i,j\in\{1,2,\ldots,n\}\). A permutation graph is a _bipartite permutation graph_[17] if it is bipartite. A Hamiltonian cycle of a bipartite permutation graph can be obtained in linear time [17]. We follow this algorithm, which uses the following vertex ordering characterization.  
Theorem 7 ([17]): _A strong ordering of a bipartite graph \(G=(U,W,E)\) is a pair of total orderings \(u_{0},u_{1},\ldots,u_{|U|-1}\) of \(U\) and \(w_{0},w_{1},\ldots,w_{|W|-1}\) of \(W\) such that for every \(i,j,k,h\) with \(0\leq i<j<|U|\) and \(0\leq k<h<|W|\), if \(u_{i}w_{h}\in E\) and \(u_{j}w_{k}\in E\) then \(u_{i}w_{k}\in E\) and \(u_{j}w_{h}\in E\). A bipartite graph is a bipartite permutation graph if and only if it has a strong ordering. Moreover, a strong ordering of a bipartite permutation graph can be obtained in linear time._  
A bipartite graph \(G=(U,W,E)\) is _balanced_ if \(|U|=|W|\). Notice that, if a bipartite permutation graph \(G\) has a Hamiltonian cycle, then \(G\) is biconnected and balanced with \(|U|=|W|\geq 2\), but the converse does not hold. See Figure 6 for example. Bipartite permutation graphs having a Hamiltonian cycle are characterized as follows.  
We finally construct \(C_{i}\) from \(C_{i-1}\) with \(i=2q+1\geq 3\). Recall that \(C_{i-1}\) contains the edges on \(C_{t}\) induced by \(\{u_{0},\ldots,u_{q-1},w_{q-1},u_{q}\}\), When \(u_{q-1}w_{q}\in E(C_{i-1})\), we define \(C_{i-1}\) as \(C_{i}\). We then consider the case when \(u_{q-1}w_{q}\
otin E(C_{i-1})\). Let \(w_{j},u_{k},u_{h}\) be the vertices of \(G\) such that  
\[C_{i-1}=(u_{q},w_{q-1},\ldots,u_{q-1},w_{j},\ldots,u_{k},w_{q},u_{h},\ldots).\]  
We have \(j>q-1\) by the definition of \(C_{i-1}\). Since \(u_{q-1}w_{q}\
otin E(C_{i-1})\), we have \(j>q\). We also have \(k,h>q-2\) by the definition of \(C_{i-1}\). Since \(u_{q-1}w_{q}\
otin E(C_{i-1})\), we have \(k,h\
eq q-1\), and thus \(k,h>q-1\). Since \(u_{q-1}w_{j},u_{h}w_{q}\in E(G)\), we have \(u_{q-1}w_{q},u_{h}w_{j}\in E(G)\) by the definition of strong orderings. We define that \(C_{i}\) is the Hamiltonian cycle obtained from \(C_{i-1}\) by switching the edges \(u_{q-1}w_{j}\) and \(u_{h}w_{q}\) with the edges \(u_{q-1}w_{q}\) and \(u_{h}w_{j}\), that is,  
\[C_{i}=(u_{q},w_{q-1},\ldots,u_{q-1},w_{q},u_{k},\ldots,w_{j},u_{h},\ldots).\]  
Therefore, we have the sequence of at most \(n-3\) switches transforming \(C_{0}\) into the canonical cycle \(C_{t}\).  
We also have the following from Theorem 9.  
Corollary 3: _For each Hamiltonian cycle of a bipartite permutation graph \(G\), we can compute a sequence of switches transforming it to the canonical cycle of \(G\) in \(O(n)\) time, provided that a strong ordering of \(G\) is given._  
Proof: The proof is similar to that of Corollary 1, and is omitted.  
Now, we have the following from Theorem 9 and Corollary 3.  
Corollary 4: _For any two Hamiltonian cycles of a bipartite permutation graph, there is a sequence of at most \(2n-6\) switches transforming one cycle to the other. Moreover, we can compute such a sequence in \(O(n)\) time, provided that a strong ordering of \(G\) is given._  
**Funding:** This research received no external funding.  
**Acknowledgments:** We are grateful to the reviewers for careful reading and helpful comments.  
**Conflicts of Interest:** The author declares no conflict of interest.