Cycles in the burnt pancake graphs

Abstract

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 $\ell$ with $6\le \ell \le n!$. The burnt pancake graph $B{P}_n$, which is the Cayley graph of the group of signed permutations $B_n$ using prefix reversals as generators, has similar properties. Indeed, $B{P}_n$ is $n$-regular and vertex-transitive. In this paper, we show that $B{P}_n$ has every cycle of length $\ell$ with $8\le \ell \le 2^{n}n!$. The proof given is a constructive one that utilizes the recursive structure of $B{P}_n$. We also present a complete characterization of all the $8$-cycles in $B{P}_n$ for $n\ge 2$, which are the smallest cycles embeddable in $B{P}_n$, by presenting their canonical forms as products of the prefix reversal generators.

Added a reference, clarified some definitions, fixed some typos. 42 pages, 9 figures, 20 pages of appendices