The Spectral Gap of Graphs Arising From Substring Reversals

Citations Over TimeTop 24% of 2017 papers

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.

Related Papers

• → The Spectral Gap of Graphs Arising From Substring Reversals(2017)13 cited
• → Using Treaps for Optimization of Graph Storage(2012)1 cited
• → 3D Human Pose Regression Using Graph Convolutional Network(2021)1 cited