Abstract: A classical and celebrated result states that two random permutations of a set of n elements almost surely generate either the symmetric or the alternating group of degree n, and similar results hold when more generators are considered. Our interest lies in describing sets of three prefix reversals that generate the entire symmetric group. The importance of fixed--degree pancake graphs, in particular, cubic pancake graphs as models of networks was shown in 2003 where cubic pancake graphs were considered as induced subgraphs of the pancake graph. In particular, the combinatorial necessary conditions for a triple of distinct prefix reversals to generate the symmetric group were identified. In this talk, we provide with necessary and sufficient conditions (in group-theoretical terms) for new generating sets.

Cite: Konstantinova E.V.
Cubic Pancake Graphs
Autumn Workshop on Algebraic Combinatorics November 8-9, 2025, Shijiazhuang, China 08-09 Nov 2025