The spectral gap of graphs arising from substring reversals

zbMath1368.05093MaRDI QIDQ2363694

Josh Tobin, Fan R. K. Chung

Publication date: 26 July 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p4

zbMATH Keywords

spectral graph theorypancake flippingprefix reversal

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (7)

Eigenvalues of Cayley graphs ⋮ On the flip graphs on perfect matchings of complete graphs and signed reversal graphs ⋮ Unnamed Item ⋮ Aldous' spectral gap property for normal Cayley graphs on symmetric groups ⋮ The second eigenvalue of some normal Cayley graphs of highly transitive groups ⋮ On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\) ⋮ The second largest eigenvalues of some Cayley graphs on alternating groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pancake flipping is hard
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Reversals Cayley graphs of symmetric groups
• Random shuffles and group representations
• Bounds for sorting by prefix reversal
• On the problem of sorting burnt pancakes
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• On certain integral Schreier graphs of the symmetric group
• Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap
• On the Diameter of the Pancake Network
• Symmetric groups and expanders
• Genome Rearrangements and Sorting by Reversals
• On Cayley graphs on the symmetric group generated by transpositions
• Polynomial-time algorithm for computing translocation distance between genomes

This page was built for publication: The spectral gap of graphs arising from substring reversals