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 P_n, 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!(n³ + 12n² − 103n + 176) / 16 distinct 8–cycles in P_n, n ≥ 4. A maximal set of independent 8–cycles contains n! / 8 of these.