Generating the symmetric group by three prefix reversals
The cubic pancake graphs are Cayley graphs over the symmetric group $\mathrm{Sym}_n$ generated by three prefix reversals. There is the following open problem: characterize all the sets of three prefix reversals that generate $\mathrm{Sym}_n$. As the largest prefix reversal of length $n$ is always included in a triple, we give a complete solution of the problem when any of the two smallest or the two largest lengths but $n$ are included in a triple of prefix reversals. Moreover, some conditions implying a triple of prefix reversals does not generate $\mathrm{Sym}_n$ are considered. Computational results on the diameter and the girth of some cubic pancake graphs are presented, and conjectures for future research are formulated. 26 pages, 4 tables, 3 figures, 27 references
Authors
- Elena V. Konstantinova (ORCID: https://orcid.org/0000-0002-3457-645X)
- Mikhail Petrovich Golubyatnikov (ORCID: https://orcid.org/0000-0002-1424-9152)
- Saúl A. Blanco (ORCID: https://orcid.org/0000-0003-2315-5331)
- Н. В. Маслова (ORCID: https://orcid.org/0000-0002-1814-0234)
- Luka A. Nikiforov
Institutions
- Indiana University Health (US)
- China Three Gorges University (CN)
- Novosibirsk State University (RU)
- Institute of Mathematics and Mechanics (AZ)
- Sobolev Institute of Mathematics (RU)
- N.N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences (RU)
- Indiana University – Purdue University Indianapolis (US)
Publication Details
- Journal
- Discrete Mathematics & Theoretical Computer Science
- Published
- 2026-09-24
- DOI
- https://doi.org/10.46298/dmtcs.16975
- Primary Topic
- Genome Rearrangement Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Ministry of Science and Higher Education of the Russian Federation