Small cycles in the Pancake graph

Elena Konstantinova, Alexey Medvedev


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.


05C15, 05C25, 05C38, 90B10

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications