Cycles of length seven in the pancake graph. (Russian) Zbl 1249.05207

Konstantinova, E. V.; Medvedev, A. N.

Diskretn. Anal. Issled. Oper. 17, No. 5, 46-55 (2010).

Summary: It was proved that a cycle \(C_l\) of length \(l\), \(6\leq l\leq n!\), can be embedded in the pancake graph \(P_n\), \(n\geq 3\), that is the Cayley graph on the symmetric group with the generating set of all prefix-reversals. We characterize the cycles of length seven in this graph and prove that each of the vertices in \(P_n\), \(n\geq 4\), belongs to \(7(n-3)\) cycles of length seven and that there are exactly \(n!(n-3)\) different cycles of length seven in the graph \(P_n\), \(n\geq 4\).

MSC:

05C38	Paths and cycles
05C25	Graphs and abstract algebra (groups, rings, fields, etc.)
20B30	Symmetric groups

Keywords:

pancake graph; Cayley graph; symmetric group; cycle embedding