×

Lengths of cycles in generalized pancake graphs. (English) Zbl 1540.05046

Summary: In this paper, we consider the lengths of cycles that can be embedded on the edges of the generalized pancake graphs which are the Cayley graph of the generalized symmetric group \(S(m, n)\), generated by prefix reversals. The generalized symmetric group \(S(m, n)\) is the wreath product of the cyclic group of order \(m\) and the symmetric group of order \(n!\). Our main focus is the underlying undirected graphs, denoted by \(\mathbb{P}_m(n)\). In the cases when the cyclic group has one or two elements, these graphs are isomorphic to the pancake graphs and burnt pancake graphs, respectively. We prove that when the cyclic group has three elements, \(\mathbb{P}_3 (n)\) has cycles of all possible lengths, thus resembling a similar property of pancake graphs and burnt pancake graphs. Moreover, \(\mathbb{P}_4(n)\) has all the even-length cycles. We utilize these results as base cases and show that if \(m > 2\) is even, \(\mathbb{P}_m (n)\) has all cycles of even length starting from its girth to a Hamiltonian cycle. Moreover, when \(m > 2\) is odd, \(\mathbb{P}_m (n)\) has cycles of all lengths starting from its girth to a Hamiltonian cycle. We furthermore show that the girth of \(\mathbb{P}_m (n)\) is \(\min \{m, 6\}\) if \(m \geq 3\), thus complementing the known results for \(m = 1, 2\).

MSC:

05C12 Distance in graphs
05C38 Paths and cycles
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B30 Symmetric groups

References:

[1] Blanco, S. A.; Buehrle, C.; Patidar, A., Cycles in the burnt pancake graph, Discrete Appl. Math., 271, 1-14 (2019) · Zbl 1428.05129
[2] Blanco, S. A.; Buehrle, C.; Patidar, A., On the number of pancake stacks requiring four flips to be sorted, Discret. Math. Theor. Comput. Sci., 21, 2 (Nov. 2019), Permutation Patters 2018 · Zbl 1437.05016
[3] Cameron, B.; Sawada, J.; Williams, A., A Hamilton cycle in the k-sided pancake network, (Flocchini, P.; Moura, L., Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings. Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12757 (2021), Springer), 137-151 · Zbl 07495019
[4] Compeau, P. E.C., Girth of pancake graphs, Discrete Appl. Math., 159, 15, 1641-1645 (2011) · Zbl 1228.05166
[5] Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 1, 47-57 (1979) · Zbl 0397.68062
[6] Gunderson, D. S., Handbook of Mathematical Induction: Theory and Applications (2010), Chapman and Hall/CRC
[7] Hannenhalli, S.; Pevzner, P. A., Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, J. ACM, 46, 1, 1-27 (1999) · Zbl 1064.92510
[8] Hawick, K. A.; James, H. A., Enumerating circuits and loops in graphs with self-arcs and multiple-arcs, (Arabnia, H. R.; Mun, Y.; Zhou, P. L., Proceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008. Proceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008, Las Vegas, Nevada, USA, July 14-17, 2008 (2008), CSREA Press), 14-20
[9] Justan, M.; Muga, F.; Sudborough, I., On the generalization of the pancake network, (Proceedings International Symposium on Parallel Architectures, Algorithms and Networks. I-SPAN’02 (2002), IEEE), 173-178
[10] Kanevsky, A.; Feng, C., On the embedding of cycles in pancake graphs, Parallel Comput., 21, 6, 923-936 (1995) · Zbl 0875.68708
[11] Kleitman, D. J.; Kramer, E.; Conway, J. H.; Bell, S.; Dweighter, H., Problems and solutions: elementary problems: E2564-E2569, Am. Math. Mon., 82, 10, 1009-1010 (1975)
[12] Konstantinova, E. V.; Medvedev, A. N., Cycles of length seven in the Pancake graph, Diskretn. Anal. Issled. Oper., 17, 5, 46-55 (2010), 95 · Zbl 1249.05207
[13] Konstantinova, E. V.; Medvedev, A. N., Cycles of length nine in the Pancake graph, Diskretn. Anal. Issled. Oper., 18, 6, 33-60 (2011), 93-94 · Zbl 1249.05208
[14] Konstantinova, E.; Medvedev, A., Independent even cycles in the pancake graph and greedy prefix-reversal gray codes, Graphs Comb., 32, 5, 1965-1978 (2016) · Zbl 1349.05198
[15] Leslie, A. (2022), Online
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.