Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The Grone-Merris Conjecture


Author: Hua Bai
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
Published electronically: March 23, 2011
MathSciNet review: 2792996
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Ravindra B. Bapat, Arbind K. Lal and Sukanta Pati, Laplacian spectrum of weakly quasi-threshold graphs, Graphs Comb. 24, no. 4 (2008), 273-290. MR 2438859 (2009g:05099)
  • 2. Fan R. K. Chung, Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics, American Mathematical Society, 1997. MR 1421568 (97k:58183)
  • 3. Art M. Duval and Victor Reiner, Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc. 354 (2002), 4313-4344. MR 1926878 (2003j:15017)
  • 4. Ky Fan, On a theorem of Weyl concerning eigenvalues of linear transformations I, Proc. Nat. Acad. Sci. USA 35 (1949), 652-655. MR 0034519 (11:600e)
  • 5. Stéhane Földes and Peter L. Hammer, `Split graphs', Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, 1977, Congressus Numerantium, XIX, Winnipeg: Utilitas Math., 311-315. MR 0505860 (58:21844)
  • 6. David Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957), 1073-1082. MR 0091855 (19:1024a)
  • 7. Robert Grone, Eigenvalues and degree sequences of graphs, Lin. Multilin. Alg. 39 (1995) 133-136. MR 1374475 (97a:05148)
  • 8. Robert Grone and Russell Merris, Coalescence, majorization, edge valuations and the Laplacian spectra of graphs, Lin. Multilin. Alg. 27, No.2 (1990), 139-146. MR 1054137 (91c:05129)
  • 9. Robert Grone and Russell Merris, The Laplacian spectrum of a graph II, SIAM J. Disc. Math. 7 (1994), 221-229. MR 1271994 (95d:05085)
  • 10. Peter L. Hammer and Bruno Simeone, The spittance of a graph, Combinatorica 1 (1981), 275-284. MR 637832 (84c:05050)
  • 11. Roger Alfred Horn, Doubly stochastic matrices and the diagonal of a rotation matrix, Amer. J. Math. 76 (1954), 620-630. MR 0063336 (16:105c)
  • 12. Nets Hawk Katz, The Grone Merris conjecture and a quadratic eigenvalue problem, preprint, 2005; arXiv:math.CA/0512647.
  • 13. Steve Kirkland, Near threshold graphs, Electron. J. Combin. 16, no. 1(2009), Research Paper R42. MR 2491644 (2010g:05221)
  • 14. Russell Merris, Laplacian matrices of graphs: a survey, Linear Algebra and its Applications 197 & 198 (1994), 143-176. MR 1275613 (95e:05084)
  • 15. Russell Merris, Split graphs, European J. Combin. 24, 4 (2003), 413-430. MR 1975945 (2004b:05064)
  • 16. Michael Reed and Barry Simon, Methods of Modern Mathematical Physics IV: Analysis of Operators, Academic Press, 1978. MR 0493421 (58:12429c)
  • 17. Herbert J. Ryser, Combinatorial properties of matrices of zeros and ones, Pacific J. Math. 7 (1957), 1073-1082. MR 0087622 (19:379d)
  • 18. Issac Schur, Uber eine Klasse von Mittelbidungen mit Anwendungen die Determinanten, Sitzungsber. Berlin. Math. Gesellschaft 22 (1923), 9-20.
  • 19. Tamon Stephen, On the Grone-Merris conjecture, DMTCS proc. AE (2005), 187-192.
  • 20. Regina I. Tyshkevich and Arkady A. Chernyak, Canonical partition of a graph defined by the degrees of its vertices, (in Russian), Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk 5 1979, 14-26. MR 554162 (81f:05098)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 15A42, 05C50

Retrieve articles in all journals with MSC (2010): 15A42, 05C50


Additional Information

Hua Bai
Affiliation: Department of Mathematics, Boston College, Chestnut Hill, Massachusetts 02467
Email: baihu@bc.edu, huabai@alumni.usc.edu

DOI: https://doi.org/10.1090/S0002-9947-2011-05393-6
Keywords: Grone-Merris Conjecture, Laplacian matrix, majorization, split graph, Courant-Fischer-Weyl Min-Max Principle, simplicial complex
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
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society