Geodesic
The girths of the cubic pancake graphs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 274-296 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TIMM_2022_28_2_a21,
     author = {Elena V. Konstantinova and Son En Gun},
     title = {The girths of the cubic pancake graphs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {274--296},
     year = {2022},
     volume = {28},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a21/}
}
TY  - JOUR
AU  - Elena V. Konstantinova
AU  - Son En Gun
TI  - The girths of the cubic pancake graphs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2022
SP  - 274
EP  - 296
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a21/
LA  - en
ID  - TIMM_2022_28_2_a21
ER  - 
%0 Journal Article
%A Elena V. Konstantinova
%A Son En Gun
%T The girths of the cubic pancake graphs
%J Trudy Instituta matematiki i mehaniki
%D 2022
%P 274-296
%V 28
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a21/
%G en
%F TIMM_2022_28_2_a21
Elena V. Konstantinova; Son En Gun. The girths of the cubic pancake graphs. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 274-296. http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a21/

[1] Bass D.W., Sudborough I.H., “Pancake problems with restricted prefix reversals and some corresponding Cayley networks”, Journal of Parallel and Distributed Computing, 63 (2003), 327–336 | DOI | Zbl

[2] Compeau P.E.C., “Girth of pancake graphs”, Discrete Appl. Math., 159 (2011), 1641–1645 | DOI | MR | Zbl

[3] Dweighter H., “E 2569. In: Elementary problems”, Amer. Math. Monthly, 82:10 (1975), 1010 | DOI | MR

[4] Kanevsky A., Feng C., “On the embedding of cycles in pancake graphs”, Parallel Computing, 21 (1995), 923–936 | DOI | MR | Zbl

[5] Konstantinova E.V., Medvedev A.N., “Cycles of length seven in the pancake graph”, Diskretnyi Analiz i Issledovanie Operatsii, 17 (2010), 46–55, (in Russian) | MR | Zbl

[6] Konstantinova E.V., Medvedev A.N., “Cycles of length nine in the pancake graph”, Diskretnyi Analiz i Issledovanie Operatsii, 18 (2011), 33–60, (in Russian) | MR | Zbl

[7] Konstantinova E., Medvedev A., “Small cycles in the pancake graph”, Ars Mathematica Contemporanea, 7 (2014), 237–246 | DOI | MR | Zbl

[8] Konstantinova E., Medvedev A., “Independent even cycles in the pancake graph and greedy Prefix-reversal Gray codes”, Graphs and Combinatorics, 32 (2016), 1965–1978 | DOI | MR | Zbl

[9] Sheu J.J., Tan J.J.M., Chu K.T., “Cycle embedding in pancake interconnection networks”, Proc. 23rd Workshop on Combinatorial Mathematics and Computation Theory (Taiwan), 2006, 85–92

[10] Sawada J., Williams A., “Successor rules for flipping pancakes and burnt pancakes”, Theoretical Computer Science, 609 (2016), 60–75 | DOI | MR | Zbl

[11] Williams A., “The greedy gray code algorithm”, Algorithms and Data Structures, Lecture Notes in Computer Science, 8037, eds. Frank Dehne et al., 2013, 525–536 | DOI | MR | Zbl