|
Diskretnyi Analiz i Issledovanie Operatsii, 2010, Volume 17, Issue 5, Pages 46–55
(Mi da624)
|
|
|
|
This article is cited in 9 scientific papers (total in 9 papers)
Cycles of length seven in the pancake graph
E. V. Konstantinovaab, A. N. Medvedevb a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
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.
Received: 03.02.2010 Revised: 01.04.2010
Citation:
E. V. Konstantinova, A. N. Medvedev, “Cycles of length seven in the pancake graph”, Diskretn. Anal. Issled. Oper., 17:5 (2010), 46–55
Linking options:
https://www.mathnet.ru/eng/da624 https://www.mathnet.ru/eng/da/v17/i5/p46
|
|