Volume 17, No 5, 2010, P. 4655
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 prefixreversals. 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(n3)$ cycles of length seven, and there are exactly $n!(n3)$ 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
email: e_konsta@math.nsc.ru, an_medvedev@yahoo.com
