Small cycles in the Pancake graph

Authors

  • Elena Konstantinova Sobolev Institute of Mathematics, Russia and Yeungnam University, South Korea
  • Alexey Medvedev Sobolev Institute of Mathematics, Russia and Central European University, Hungary

DOI:

https://doi.org/10.26493/1855-3974.214.0e8

Keywords:

05C15, 05C25, 05C38, 90B10

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.

Published

2013-04-24

Issue

Section

Special Issue Bled'11