Generating the symmetric group by three prefix reversals | Sciact - Система учета научной деятельности ИМ СО РАН

Generating the symmetric group by three prefix reversals Научная публикация

Журнал

Discrete Mathematics and Theoretical Computer Science
ISSN: 1365-8050

Вых. Данные

Год: 2026, Том: 28, Номер: 1, Номер статьи : 7, Страниц : 24 DOI: 10.46298/dmtcs.16975

Ключевые слова

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

Авторы

Konstantinova Elena V. ^1,2,3

Организации

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

Информация о финансировании (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

Поступила в редакцию:	24 нояб. 2025 г.
Принята к публикации:	13 сент. 2026 г.
Опубликована online:	24 сент. 2026 г.

≡ OpenAlex:

W4416667267