2018/08/14 by Saúl A. Blanco, Blanco, Saúl A., Charles Buehrle +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C25 #05C45 #68R10 #Algorithms and Data Compression #C.2.1 #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Genome Rearrangement Algorithms #Group Theory (math.GR)
paper · pdf · doi:10.48550/arxiv.1808.04890
openalex publication_date 2018/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The pancake graph Pn is the Cayley graph of the symmetric group Sn on n elements generated by prefix reversals. Pn has been shown to have properties that makes it a useful network scheme for parallel processors. For example, it is (n-1)-regular, vertex-transitive, and one can embed cycles in it of length ℓ with 6≤ℓ≤ n!. The burnt pancake graph BPn, which is the Cayley graph of the group of signed permutations Bn using prefix reversals as generators, has similar properties. Indeed, BPn is n-regular and vertex-transitive. In this paper, we show that BPn has every cycle of length ℓ with 8≤ℓ≤ 2n n!. The proof given is a constructive one that utilizes the recursive structure of BPn. We also present a complete characterization of all the 8-cycles in BPn for n ≥ 2, which are the smallest cycles embeddable in BPn, by presenting their canonical forms as products of the prefix reversal generators.