The spectral gap of graphs arising from substring reversals (Q2363694)

Summary: 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.