Volume 17, No 5, 2010, P. 46-55
UDC 519.174
E. V. Konstantinova, A. N. Medvedev
Cycles of length seven in the pancake graph
Abstract:
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\geq3$ , that is the Cayley graph on the symmetric group with the generating set of all prefix-reversals. In this paper the characterization of cycles of length seven in this graph is given. It is proved that each of the vertices in$P_n$ ,$n\geq4$ , belongs to$7(n-3)$ cycles of length seven, and there are exactly$n!(n-3)$ different cycles of length seven in the graph$P_n$ ,$n\geq4$ .
Ill. 1, tab. 1, bibliogr. 7.
Keywords: the pancake graph, Cayley graph, the symmetric group, cycle embedding.
Konstantinova Elena Valentinovna 1,2
Medvedev Alexey Nikolaevich 2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: e_konsta@math.nsc.ru, an_medvedev@yahoo.com
