The Spectral Gap of Graphs Arising From Substring Reversals

Electronic Journal Of Combinatorics

Fan Chung¹ 

关键词: Spectral graph theory;    Pancake flipping;    Prefix reversal;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

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 spectru

【 授权许可】

Others