The Spectral Gap of Graphs Arising From Substring Reversals

Fan Chung, Josh Tobin

Abstract


The substring reversal graph $R_n$ is the graph whose vertices are the permutations $S_n$, and where two permutations are adjacent if one is obtained from a substring reversal of the other. We determine the spectral gap of $R_n$, and show that its spectrum contains many integer values. Further we consider a family of graphs that generalize the prefix reversal (or pancake flipping) graph, and show that every graph in this family has adjacency spectral gap equal to one.


Keywords


Spectral graph theory; Pancake flipping; Prefix reversal

Full Text: PDF