On the spectra of prefix-reversal graphs

Abstract

In this paper, we study spectral properties of prefix-reversal graphs. These graphs are obtained by connecting two elements of $C_m\wr S_n$ 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 ${\mathbb{P}}_m(n)$ contains all even integers in the interval $[0,2n]\setminus \{2\lfloor n/2\rfloor \}$ and if $m\equiv 0(\mathrm{mod}4)$, 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]\setminus \{\lfloor n/2\rfloor \}$. As a consequence, we show that in either case, the prefix-reversal graphs have a small spectral gap.

18 pages