Generating the symmetric group by three prefix reversals

Generating the symmetric group by three prefix reversals Full article

Journal

Discrete Mathematics and Theoretical Computer Science
ISSN: 1365-8050

Output data

Year: 2026, Volume: 28, Number: 1, Article number : 7, Pages count : 24 DOI: 10.46298/dmtcs.16975

Tags

cubic pancake graph, prefix reversal, generating set, symmetric group

Authors

Konstantinova Elena V. ^1,2,3

Affiliations

1	Sobolev Institute of Mathematics
2	Novosibirsk State University
3	China Three Gorges University
4	Indiana University
5	N.N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences
6	Ural Mathematical Center

Funding (1)

Министерство науки и высшего образования РФ

075-15-2025-348

The cubic pancake graphs are Cayley graphs over the symmetric group Sym_n generated by three prefix reversals. There is the following open problem: characterize all the sets of three prefix reversals that generate 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 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.

Konstantinova E.V.
Generating the symmetric group by three prefix reversals
Discrete Mathematics and Theoretical Computer Science. 2026. V.28. N1. 7 :1-24. DOI: 10.46298/dmtcs.16975 OpenAlex

Submitted:	Nov 24, 2025
Accepted:	Sep 13, 2026
Published online:	Sep 24, 2026

≡ OpenAlex:

W4416667267