Small cycles in the Pancake graph
Abstract
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.
Keywords
05C15, 05C25, 05C38, 90B10
DOI: https://doi.org/10.26493/1855-3974.214.0e8
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