2025/06/10 by Saúl A. Blanco, Blanco, Saúl A., Charles Buehrle +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Mathematics · #05C50 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #G.2.1 #G.2.2 #Genome Rearrangement Algorithms #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2506.08345
openalex publication_date 2025/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study spectral properties of prefix-reversal graphs. These graphs are obtained by connecting two elements of Cm\wr Sn via prefix reversals. If m=1,2, the corresponding prefix-reversal graphs are the classic pancake and burnt pancake graphs. If m>2, then one can consider the directed and undirected versions of these graphs. We prove that the spectrum of the undirected prefix-reversal graph ℙm(n) contains all even integers in the interval [0,2n]∖\2\lfloor n/2\rfloor\ and if m≡0\pmod4, we then show that the spectrum contains all even integers in [0,2n]. In the directed case, we show that the spectrum of the directed prefix-reversal graph P(m,n) contains all integers in the interval [0,n]∖\\lfloor n/2\rfloor\. As a consequence, we show that in either case, the prefix-reversal graphs have a small spectral gap.