Small cycles in the Pancake graph
DOI:
https://doi.org/10.26493/1855-3974.214.0e8Keywords:
05C15, 05C25, 05C38, 90B10Abstract
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.
Downloads
Published
2013-04-24
Issue
Section
Special Issue Bled'11
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/