Independent Even Cycles in the Pancake Graph and Greedy Prefix-Reversal Gray Codes

Elena Konstantinova, Alexey Medvedev

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)1965-1978
Number of pages14
JournalGraphs and Combinatorics
Volume32
Issue number5
DOIs
Publication statusPublished - 1 Sep 2016
Externally publishedYes

Keywords

  • Disjoint cycle cover
  • Even cycles
  • Fastening cycle
  • Pancake graph
  • Pancake sorting
  • Prefix-reversal Gray codes

Fingerprint Dive into the research topics of 'Independent Even Cycles in the Pancake Graph and Greedy Prefix-Reversal Gray Codes'. Together they form a unique fingerprint.

  • Cite this