Small cycles in the Pancake graph
Keywords:05C15, 05C25, 05C38, 90B10
The Pancake graph is well known because of the open Pancake problem. It has the structure that any l–cycle, 6 ≤ l ≤ n!, can be embedded in the Pancake graph Pn, n ≥ 3. Recently it was shown that there are exactly 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 n!(n3 + 12n2 − 103n + 176) / 16 distinct 8–cycles in Pn, n ≥ 4. A maximal set of independent 8–cycles contains n! / 8 of these.
Special Issue Bled'11
Articles in this journal are published under Creative Commons Attribution 4.0 International License