Cycles in the burnt pancake graph

The pancake graph P-n is the Cayley graph of the symmetric group S-n on n elements generated by prefix reversals. P-n 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 l with 6 <= l <= n!. The burnt pancake graph BPn, which is the Cayley graph of the group of signed permutations B-n 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 l with 8 <= l <= 2(n)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. (C) 2019 Elsevier B.V. All rights reserved.