Hamilton Cycles in Restricted and Incomplete Rotator Graphs

Abstract

The nodes of a rotator graph are the permutations of n, and an arc is directed from u to v if the first r symbols of u can be rotated one position to the left to obtain v. Restricted rotator graphs restrict the allowable rotations to r ∈ R for some R ⊆ {2,3,…,n}. Incomplete rotator graphs only include nodes whose final symbol is i ≤ m for a fixed maximum value m ∈ {1,2,…,n}. Restricted rotator graphs are directed Cayley graphs, whereas incomplete rotator graphs are not Cayley graphs. Hamilton cycles exist for rotator graphs (Corbett 1992), restricted rotator graphs with R={n−1,n} (Ruskey and Williams 2010), and incomplete rotator graphs for all m (Ponnuswamy and Chaudhary 1994). These previous results are based on sequence building operations that we name `reusing', `recycling', and `rewinding'. In this article, we combine these operations to create Hamilton cycles in rotator graphs that are (1) restricted by R={2,3,n}, (2) restricted by R={2,3,n−1,n} and incomplete for any m, and (3) restricted by R={n−2,n−1,n} and incomplete for any m. Result (1) is `optimal' since restricted rotator graphs are not strongly connected for R={3,n} when n is odd, and do not have Hamilton cycles for R={2,n} when n is even (Rankin 1944, Swan 1999). Similarly, we prove (3) is `optimal'. Our Hamilton cycles can be easily implemented for potential applications, and we provide O(1)-time algorithms that generate successive rotations for (1)-(3).