Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00278
Hamilton Cycles in Restricted and Incomplete Rotator Graphs
Brett Stevens and
Aaron Williams
Vol. 16, no. 4, pp. 785-810, 2012. Regular paper.
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).
|
Submitted: February 2012.
Reviewed: May 2012.
Revised: September 2012.
Accepted: September 2012.
Final: September 2012.
Published: October 2012.
Communicated by
Dorothea Wagner
|
Journal Supporters
|