MSC: 05C25, 05C38, 05C82, 68R10
DOI: 10.21538/0134-4889-2022-28-2-274-296
Полный текст статьи (Full text)
This paper is based on the results of the 2021 Conference of International Mathematical Centers “Groups and Graphs, Semigroups and Synchronization”.
The pancake graphs $P_n, n\geqslant 2$, are Cayley graphs over the symmetric group $\mathrm{Sym}_n$ generated by prefix-reversals. There are six generating sets of prefix-reversals of cardinality three which give connected Cayley graphs over the symmetric group known as cubic pancake graphs. In this paper we study the girth of the cubic pancake graphs. It is proved that considered cubic pancake graphs have the girths at most twelve.
Keywords: pancake graph, cubic pancake graph, prefix-reversal, girth
REFERENCES
1. Bass D.W., Sudborough I.H. Pancake problems with restricted prefix reversals and some corresponding Cayley networks. Journal of Parallel and Distributed Computing, 2003, vol. 63, pp. 327–336. doi: 10.1016/S0743-7315(03)00033-9
2. Compeau P.E.C. Girth of pancake graphs. Discrete Appl. Math., 2011, vol. 159, pp. 1641–1645. doi: 10.1016/j.dam.2011.06.013
3. Dweighter H. E 2569. In: Elementary problems. Amer. Math. Monthly, 1975, vol. 82, no. 10, p. 1010. doi: 10.1080/00029890.1975.11994014
4. Kanevsky A., Feng C. On the embedding of cycles in pancake graphs. Parallel Computing, 1995, vol. 21, no. 923–936. doi: 10.1016/0167-8191(94)00096-S
5. Konstantinova E.V., Medvedev A.N. Cycles of length seven in the pancake graph. Diskretnyi Analiz i Issledovanie Operatsii, 2010, vol. 17, pp. 46–55 (in Russian).
6. Konstantinova E.V., Medvedev A.N. Cycles of length nine in the pancake graph. Diskretnyi Analiz i Issledovanie Operatsii, 2011, vol. 18, pp. 33–60 (in Russian).
7. Konstantinova E., Medvedev A. Small cycles in the pancake graph. Ars Mathematica Contemporanea, 2014, vol. 7, pp. 237–246. doi: 10.26493/1855-3974.214.0e8
8. Konstantinova E., Medvedev A. Independent even cycles in the pancake graph and greedy Prefix-reversal Gray codes. Graphs and Combinatorics, 2016, vol. 32, pp. 1965–1978. doi: 10.1007/s00373-016-1679-x
9. Sheu J.J., Tan J.J.M., Chu K.T. Cycle embedding in pancake interconnection networks. In: Proc. 23rd Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 2006, pp. 85–92.
10. Sawada J., Williams A. Successor rules for flipping pancakes and burnt pancakes. Theoretical Computer Science, 2016, vol. 609, pp. 60–75. doi: 10.1016/j.tcs.2015.09.007
11. Williams A. The greedy gray code algorithm. In: Algorithms and Data Structures, eds. Frank Dehne et al., 2013, Lecture Notes in Computer Science, vol. 8037, pp. 525–536. doi: 10.1007/978-3-642-40104-6_46
Received December 30, 2021
Revised March 1, 2022
Accepted March 10, 2022
Funding Agency: The first author is supported by the project No. FWNF-2022-0017 (the state contract of the Sobolev Institute of Mathematics). The second author is partially supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation.
Elena Valentinovna Konstantinova, Candidate of Engineering Sciences, Sobolev Institute of Mathematics, Novosibirsk State University, Novosibirsk, 630090 Russia, e-mail: e_konsta@math.nsc.ru
Son En Gun, graduate student, Novosibirsk State University, Novosibirsk, 630090 Russia, e-mail: croxall98@gmail.com, e.son@g.nsu.ru
Cite this article as: Elena V. Konstantinova, Son En Gun. The Girths of the Cubic Pancake Graphs. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 274–296.
Русский
Е.В. Константинова, Сон Ен Гун. Обхваты кубических блинных графов
Блинный граф $P_n$, $n\geqslant 2$, — это граф Кэли над симметрической группой Sym$_n$, порожденный операцией инверсии префикса. Существует шесть порождающих множеств инверсий префиксов мощности $3$, которые приводят к связным графам Кэли над симметрической группой, известным под названием кубических блинных графов. В статье изучается обхват кубических графов Кэли. Доказано, что рассматриваемые кубические блинные графы имеют обхват не больше $12$.
Ключевые слова: блинный граф, кубический блинный граф, инверсия префикса, обхват
