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$. 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 also considered. Computational results on the diameter and the girth of some cubic pancake graphs are presented, and conjectures for future research are formulated.
From: Elena Konstantinova V. [view email]
[v1]
Fri, 21 Nov 2025 05:20:27 UTC (718 KB)
[v2]
Tue, 1 Sep 2026 07:03:14 UTC (939 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。