Abstract:In spectral graph theory, the Grone-Merris Conjecture asserts that the spectrum of the Laplacian matrix of a finite graph is majorized by the conjugate degree sequence of this graph. We give a complete proof for this conjecture.
- R. B. Bapat, A. K. Lal, and Sukanta Pati, Laplacian spectrum of weakly quasi-threshold graphs, Graphs Combin. 24 (2008), no. 4, 273–290. MR 2438859, DOI 10.1007/s00373-008-0785-9
- Fan R. K. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. MR 1421568
- Art M. Duval and Victor Reiner, Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc. 354 (2002), no. 11, 4313–4344. MR 1926878, DOI 10.1090/S0002-9947-02-03082-9
- Ky Fan, On a theorem of Weyl concerning eigenvalues of linear transformations. I, Proc. Nat. Acad. Sci. U.S.A. 35 (1949), 652–655. MR 34519, DOI 10.1073/pnas.35.11.652
- Stéphane Foldes and Peter L. Hammer, Split graphs, Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, No. XIX, Utilitas Math., Winnipeg, Man., 1977, pp. 311–315. MR 0505860
- David Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957), 1073–1082. MR 91855
- Robert D. Grone, Eigenvalues and the degree sequences of graphs, Linear and Multilinear Algebra 39 (1995), no. 1-2, 133–136. MR 1374475, DOI 10.1080/03081089508818384
- Robert Grone and Russell Merris, Coalescence, majorization, edge valuations and the Laplacian spectra of graphs, Linear and Multilinear Algebra 27 (1990), no. 2, 139–146. MR 1054137, DOI 10.1080/03081089008818004
- Robert Grone and Russell Merris, The Laplacian spectrum of a graph. II, SIAM J. Discrete Math. 7 (1994), no. 2, 221–229. MR 1271994, DOI 10.1137/S0895480191222653
- Peter L. Hammer and Bruno Simeone, The splittance of a graph, Combinatorica 1 (1981), no. 3, 275–284. MR 637832, DOI 10.1007/BF02579333
- Alfred Horn, Doubly stochastic matrices and the diagonal of a rotation matrix, Amer. J. Math. 76 (1954), 620–630. MR 63336, DOI 10.2307/2372705
- Nets Hawk Katz, The Grone Merris conjecture and a quadratic eigenvalue problem, preprint, 2005; arXiv:math.CA/0512647.
- Steve Kirkland, Near threshold graphs, Electron. J. Combin. 16 (2009), no. 1, Research Paper 42, 20. MR 2491644
- Russell Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994), 143–176. Second Conference of the International Linear Algebra Society (ILAS) (Lisbon, 1992). MR 1275613, DOI 10.1016/0024-3795(94)90486-3
- Russell Merris, Split graphs, European J. Combin. 24 (2003), no. 4, 413–430. MR 1975945, DOI 10.1016/S0195-6698(03)00030-1
- Michael Reed and Barry Simon, Methods of modern mathematical physics. IV. Analysis of operators, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. MR 0493421
- H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canadian J. Math. 9 (1957), 371–377. MR 87622, DOI 10.4153/CJM-1957-044-3
- Issac Schur, Uber eine Klasse von Mittelbidungen mit Anwendungen die Determinanten, Sitzungsber. Berlin. Math. Gesellschaft 22 (1923), 9–20.
- Tamon Stephen, On the Grone-Merris conjecture, DMTCS proc. AE (2005), 187–192.
- R. I. Tyškevič and A. A. Černjak, Canonical decomposition of a graph determined by the degrees of its vertices, Vestsī Akad. Navuk BSSR Ser. Fīz.-Mat. Navuk 5 (1979), no. 5, 14–26, 138 (Russian, with English summary). MR 554162
- Hua Bai
- Affiliation: Department of Mathematics, Boston College, Chestnut Hill, Massachusetts 02467
- Email: firstname.lastname@example.org, email@example.com
- Received by editor(s): November 12, 2009
- Received by editor(s) in revised form: December 11, 2009, January 1, 2010, and May 28, 2010
- Published electronically: March 23, 2011
- Additional Notes: The author was partially supported by NSF grant DMS-0604866
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
- Journal: Trans. Amer. Math. Soc. 363 (2011), 4463-4474
- MSC (2010): Primary 15A42; Secondary 05C50
- DOI: https://doi.org/10.1090/S0002-9947-2011-05393-6
- MathSciNet review: 2792996