The pancake graph of $S_n$, the symmetric group on $n$ elements, has been shown to have many interesting properties that makes it a useful network scheme for parallel processors. For example, it is $(n-1)$-regular, vertex-transitive, and pancyclic (one can find cycles of any length from its girth up to the number of vertices of the graph). The burnt pancake graph $BP_n$, which is obtained as the Cayley graph of the group $B_n$ of signed permutations on $n$ elements using prefix reversal as generators, has similar properties. Indeed, $BP_n$ is $n$-regular and vertex-transitive. In this paper, we show that $BP_n$ is also pancyclic. Our proof is a recursive construction of the cycles.
We also present a complete characterization of all the $8$-cycles in $BP_n$ for $n \geq 2$ by presenting their canonical forms as products of the prefix reversal generators.
from cs updates on arXiv.org https://ift.tt/2MtuzOQ
//
0 comments:
Post a Comment