RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2010, Volume 17, Number 5, Pages 46–55 (Mi da624)  

This article is cited in 4 scientific papers (total in 4 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:

Document Type: Article
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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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:
    1. E. V. Konstantinova, A. N. Medvedev, “Tsikly dliny devyat v Pancake grafe”, Diskretn. analiz i issled. oper., 18:6 (2011), 33–60  mathnet  mathscinet  zmath
    2. Konstantinova E., Medvedev A., “Small Cycles in the Pancake Graph”, ARS Math. Contemp., 7:1, SI (2014), 237–246  mathscinet  zmath  isi  elib
    3. Elena V. Konstantinova, Alexey N. Medvedev, “Small cycles in the star graph”, Sib. elektron. matem. izv., 11 (2014), 906–914  mathnet
    4. Alexey N. Medvedev, “The number of small cycles in the Star graph”, Sib. elektron. matem. izv., 13 (2016), 286–299  mathnet  crossref
  • Дискретный анализ и исследование операций
    Number of views:
    This page:251
    Full text:60
    References:19
    First page:7

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017