|
This article is cited in 5 scientific papers (total in 5 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.
Full text:
PDF file (255 kB)
References:
PDF file
HTML file
Bibliographic databases:
UDC:
519.174 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
Citation in format AMSBIB
\Bibitem{KonMed10}
\by E.~V.~Konstantinova, A.~N.~Medvedev
\paper Cycles of length seven in the pancake graph
\jour Diskretn. Anal. Issled. Oper.
\yr 2010
\vol 17
\issue 5
\pages 46--55
\mathnet{http://mi.mathnet.ru/da624}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2779351}
\zmath{https://zbmath.org/?q=an:1249.05207}
Linking options:
http://mi.mathnet.ru/eng/da624 http://mi.mathnet.ru/eng/da/v17/i5/p46
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:
-
E. V. Konstantinova, A. N. Medvedev, “Tsikly dliny devyat v Pancake grafe”, Diskretn. analiz i issled. oper., 18:6 (2011), 33–60
-
Konstantinova E., Medvedev A., “Small Cycles in the Pancake Graph”, ARS Math. Contemp., 7:1, SI (2014), 237–246
-
Elena V. Konstantinova, Alexey N. Medvedev, “Small cycles in the star graph”, Sib. elektron. matem. izv., 11 (2014), 906–914
-
Alexey N. Medvedev, “The number of small cycles in the Star graph”, Sib. elektron. matem. izv., 13 (2016), 286–299
-
Blanco S.A. Buehrle Ch. Patidar A., “Cycles in the Burnt Pancake Graph”, Discret Appl. Math., 271 (2019), 1–14
|
Number of views: |
This page: | 486 | Full text: | 121 | References: | 36 | First page: | 7 |
|