Algebraic representation of small cycles in the Pancake graph
Presented by Elena KONSTANTINOVA
Type: Oral presentation
Track: Cayley Graphs
The Pancake graph P_n which is well known because of the open Pancake problem is the Cayley graph on the symmetric group with the generating set of all prefix-reversals. It was proved [A. Kanevsky, C. Feng, Paral. Comput. 21 (1995) 923-936; J.J. Sheu, J.J. M. Tan, K.T. Chu, Proc. 23rd Workshop on Comb. Math. Comput. Theory, 2006, 85-92] that cycles of length l, 6 <= l <= n!, can be embedded in P_n, n >=3. In this paper we give an explicit description of all cycles of small length l, 6 <= l <= 9, via products of generating elements. In particular, for l=7 it is proved that each of vertices of P_n, n >=4, belongs to 7(n-3) cycles of length seven, and there are exactly n!(n-3) different cycles of length seven in the graph. Similar results are given for other cycles. We also discuss a general case.