The Grone-Merris Conjecture

Bai, Hua

doi:10.1090/S0002-9947-2011-05393-6

The Grone-Merris Conjecture
HTML articles powered by AMS MathViewer

by Hua Bai PDF

Trans. Amer. Math. Soc. 363 (2011), 4463-4474 Request permission

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.

References

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