The spectral gap of graphs arising from substring reversals. (English) Zbl 1368.05093
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.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | H. Dweighter. Problem E2569. Amer. Math. Monthly, 82:1010, 1975. |
| [2] | V. Bafna, P. Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25(2):272-289, 1996. · Zbl 0844.68123 |
| [3] | L. Bulteau, G. Furtin, I. Rusu. Pancake Flipping is Hard. Journal of Computer and System Sciences, 81(8):1556-1574, 2015. · Zbl 1328.68084 |
| [4] | F Cesi. Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap. The Electronic Journal of Combinatorics, 16(1), #N29 2009. · Zbl 1185.05079 |
| [5] | B. Chitturi, W. Fahle, Z. Meng, L. Morales, C.O. Shields, I.H. Sudborough, W. Voit. An upper bound for sorting by prefix reversals.Theoretical Computer Science, 410(36):3372, 2009. · Zbl 1191.68219 |
| [6] | F. Chung, S.-T. Yau. Coverings, heat kernels and spanning trees. Journal of Combinatorics, 6:163-184, 1998. |
| [7] | F. Chung, Spectral Graph Theory, AMS Publications, Providence, 1997. · Zbl 0867.05046 |
| [8] | D. Cohen, M. Blum. On the problem of sorting burnt pancakes. Discrete Applied Mathematics, 61(2):105-120, 1995. · Zbl 0831.68029 |
| [9] | L. Flatto, A.M. Odlyzko, D.B. Wales. Random shuffles and group representations. The Annals of Probability, 13: 154-178, 1985. · Zbl 0564.60007 |
| [10] | J. Friedman. On Cayley graphs on the symmetric group generated by tranpositions. Combinatorica, 20(4):505-519, 2000. · Zbl 0996.05066 |
| [11] | W. Gates, C. Papadimitriou.Bounds For Sorting By Prefix Reversal.Discrete Mathematics, 27:47-57, 1979. · Zbl 0397.68062 |
| [12] | C. Godsil, G. Royle. Algebraic Graph Theory, Springer, New York, 2001. · Zbl 0968.05002 |
| [13] | J. Gross, T. Tucker, Topological graph theory, Courier Corporation (1987). · Zbl 0621.05013 |
| [14] | P.E. Gunnells, R.A. Scott, B.L. Walden. On certain integral Schreier graphs of the symmetric group. The Electronic Journal of Combinatorics, 14(1) #R43 (2007). · Zbl 1123.05048 |
| [15] | S. Hannenhalli.Polynomial-time algorithm for computing translocation distance between genomes. Discrete Applied Mathematics, 71(1-3):137-151, 1996. · Zbl 0881.92020 |
| [16] | M.H. Heydari, I.H. Sudborough. On the diameter of the pancake network. J. Algorithms, 25(1):67-94, 1997. the electronic journal of combinatorics 23(3) (2017), #P3.417 · Zbl 0888.68007 |
| [17] | M. Kassabov. Symmetric groups and expanders. Electronic Research Announcements of the American Mathematical Society, 11(6), 2005. · Zbl 1077.20001 |
| [18] | J. Kececioglu, D. Sankof. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica 13:180-210, 1995. · Zbl 0831.92014 |
| [19] | R. Li, J. Meng. Reversals Cayley graphs of symmetric groups. Information Processing Letters, 109(2) (2008). · Zbl 1189.05075 |
| [20] | A. Lubotzky. Cayley graphs: eigenvalues, expanders and random walks. London Mathematical Society Lecture Note Series, 155-190, 1995. · Zbl 0835.05033 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
