Small cycles in the Pancake graph - Konstantinova, Elena (Ars mathematica contemporanea, 2014)
The Pancake graph is well known because of the open Pancake problem. It has the structure that any ?$l$?-cycle, ?$6 \leqslant l \leqslant n!$?, can be embedded in the Pancake graph ?$P_n$?, ?$n \geqslant 3$?. Recently it was shown that there are exactly ?$\frac{n!}{6}$? independent 6-cycles and ?$n!(n - 3)$? distinct 7-cycles in the graph. In this paper we characterize all distinct 8-cycles by giving their canonical forms as products of generating elements. It is shown that there are exactly ?$\frac{n!(n^3 + 12n^2 - 103n + 176)}{16}$? distinct 8-cycles in ?$P_n$?, ?$n \geqslant 4$?. A maximal set of independent 8-cycles contains? $\frac{n!}{8}$? of these.
Keywords: Cayley graphs; cycle embedding; grafi; Pancake graph; small cycles