Abstract
The Pancake graph Pn,n⩾3, is a Cayley graph on the symmetric group generated by prefix-reversals. It is known that Pn contains any ℓ-cycle for 6 ⩽ ℓ⩽ n!. In this paper we construct a family of maximal (covering) sets of even independent (vertex-disjoint) cycles of lengths ℓ bounded by O(n2). We present the new concept of prefix-reversal Gray codes based on independent cycles which extends the known greedy prefix-reversal Gray code constructions given by Zaks and Williams. Cases of non-existence of codes based on the presented family of independent cycles are provided using the fastening cycle approach. We also give necessary condition for existence of greedy prefix-reversal Gray codes based on the independent cycles with arbitrary even lengths.
Original language | English |
---|---|
Pages (from-to) | 1965-1978 |
Number of pages | 14 |
Journal | Graphs and Combinatorics |
Volume | 32 |
Issue number | 5 |
DOIs | |
Publication status | Published - 1 Sept 2016 |
Externally published | Yes |
Keywords
- Disjoint cycle cover
- Even cycles
- Fastening cycle
- Pancake graph
- Pancake sorting
- Prefix-reversal Gray codes