Lengths of Cycles in Generalized Pancake Graphs

In this paper, we consider the lengths of cycles that can be embedded on the edges of the \emph{generalized pancake graph} which is the Cayley graph of the generalized symmetric group, the wreath product of the cyclic group $C_m$ and the symmetric group, generated by prefix reversals. In the cases when the cyclic group has one or two elements the graphs are the \emph{pancake graphs} and \emph{burnt pancake graphs}, respectively. We prove that when the cyclic group has three elements the underlying, undirected graph of the generalized pancake graph is pancyclic, thus resembling a similar property of the pancake graphs and the burnt pancake graphs. Moreover, when the cyclic group has four elements, the resulting undirected graphs will have all the even-length cycles. We utilize these results as base cases and show that if $m>2$ is even, the corresponding undirected pancake graph has all cycles of even length starting from its girth to a Hamiltonian cycle. Moreover, when $m$ is odd, the corresponding undirected pancake graph has cycles of all lengths starting from its girth to a Hamiltonian cycle. We furthermore show that the girth of the undirected generalized pancake graphs is $\min\{m,6\}$ if $m\geq3$, thus complementing the known results for $m=1,2.$Comment: Added Lemma 4.1, corrected the girth results of Section 4 reporting the girth of $\mathbb{P}_m(n)$, with $m\geq3,n\geq2$ as $\min\{m,6\}$ from what was originally reported in error as $\min\{m,8\}$, and fixed typo