Generating the symmetric group by three prefix reversals
Authors
Saúl A. Blanco
Mikhail P. Golubyatnikov
Elena V. Konstantinova
Natalia V. Maslova
Luka A. Nikiforov
Abstract
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$. We present a partial answer to this problem, in particular, we characterize all generating sets of three elements that contain at least one of the prefix reversals $r_2, r_3, r_{n-2}$, and $r_{n-1}$. We also give some computational results relating to the diameter and the girth of some cubic pancake graphs.
