R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994), 143-176. Math Reviews 95e: 05084. Work leading to this article was supported by NSA grant MDA904-90-H-4024. The article was prepared in connection with the author's invited talk at the 1992 conference of the International Linear Algebra Society in Lisbon. Publication 98 is a sequel.

Status of

  • Conjecture 2.2: Resolved in the affirmative. See R. D. Grone, Eigenvalues and the degree sequences of graphs, Linear & Multilinear Algebra 39 (1995), 133-136.
  • Conjecture 2.4: Still open. Additional confirming evidence for the conjecture has been obtained by A. M. Duval and V. Reiner [Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc. 354 (2002), 4313-4344] who proved that the sum of the two largest eigenvalues of L(G) is bounded above by the sum of the two largest integers in the conjugate degree sequence, and by Tamon Stephen [A majorization bound for the eigenvalues of some graph Laplacians, manuscript] who proved the conjecture for regular graphs and trees.
  • Conjecture 6.5: Resolved in the affirmative. See O. Chan and T. K. Lam, Hook immanantal inequalities for Laplacians of trees, Linear Algebra Appl. 261 (1997), 23-47, and O. Chan and T. K. Lam, Hook immanantal inequalities for trees explained, Linear Algebra Appl. 273 (1998), 119-131.

    • Among the publications citing this article are

  • I. Gutman, Y. N. Yeh, S. L. Lee, and Y. L. Luo, Indian J. Chemistry (Section A) 32 (1993), 651-661.

  • I. Gutman, S. L. Lee, G. H. Chu, and Y. L. Luo, Indian J. Chemistry (Section A) 33 (1994), 603-608.
  • J. W. Grossman, D. M. Kulkarni and I. E. Schochetman, Linear Algebra Appl. 212/213 (1994), 289-307.

  • R. Grone, Linear & Multilinear Algebra 39 (1995), 133-136.
  • B. Y. Yang and Y. N. Yeh, Advances in Applied Math. 16 (1995), 72-94.
  • D. Veljan, Croatica Chemica Acta 68 (1995), 39-52.
  • J. Vandenheuval, Linear Algebra Appl. 228 (1995), 723-730.
  • I. Faria, Linear Algebra Appl. 229 (1995), 15-35.
  • D. Cvetkovic and S. Simic, Filomat (Nis) 9 (1995), 449-472.
  • D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs 3rd. ed., Johann Ambrosius Barth, Heidelberg, 1995.

  • S. Kirkland, M. Neumann, and B. L. Shader, Linear & Multilinear Algebra 40 (1996), 311-325.
  • I. Gutman, Bulletin de l'Academie Serbe des Sciences et des Arts, Sciences mathematiques 21 (1996), 19-29.
  • I. Gutman and B. Mohar, J. Chem. Inf. & Comp. Sci. 36 (1996), 982-985.
  • C. A. Athanasiades, J. Algebraic Combinatorics 5 (1996), 5-11.
  • R. B. Bapat, The Mathematics Student [Madras] 65 (1996), 214-223.
  • J. Klerlein, S. Sportsman, and C. Wallis, Congressus Numerantium 118 (1996), 185-191.

  • G. P. H. Styan and G. Subak-Sharpe, Linear Algebra Appl. 250 (1997), 349-370.
  • D. J. Klein, Communications in Mathematical and in Computer Chemistry 35 (1997), 7-27.
  • O. Chan and T. K. Lam, Linear Algebra Appl. 261 (1997), 23-47.
  • S. Kirkland and M. Neumann, Linear & Multilinear Algebra 42 (1997), 187-203.
  • S. J. Kirkland, M. Neumann, and B. L. Shader, SIAM J. Matrix Anal. Appl. 18 (1997), 827-841.
  • W. C. Huang, B. Y. Yang, and Y. N. Yeh, Discrete Applied Math. 73 (1997), 113-131.
  • J.-S. Li and X.-D. Zhang, Linear Algebra Appl. 265 (1997), 93-100.
  • D. Cvetkovic, P. Rowlinson, & S. Simic, Eigenspaces of Graphs, Encyclopedia of Mathematics and Its Applications 66, Cambridge University Press, 1997.
  • R. B. Bapat and T. E. S. Raghavan, Nonnegative Matrices and Applications, Encyclopedia of Mathematics and Its Applications 64, Cambridge University Press, 1997.
  • R. B. Bapat, Linear & Multilinear Algebra 42 (1997), 159-167.
  • S. Klavzar and I. Gutman, Discrete Applied Math. 80 (1997), 73-81.

  • O. Chan and T. K. Lam, Linear Algebra Appl. 273 (1998), 119-131.
  • L. Petingi, F. Boesch, and C. Suffel, Discrete Math. 179 (1998), 155-166.
  • S. Fallat and S. Kirkland, Electronic J. Linear Algebra 3 (1998), 48-74.
  • S. Kirkland and S. Fallat, Linear & Multilinear Algebra 44 (1998), 131-148.
  • M. H. Lee, Linear & Multilinear Algebra 45 (1998), 219-233.
  • R. B. Bapat and S. Pati, Linear & Multilinear Algebra 45 (1998), 247-273.
  • S. Kirkland, M. Neumann, and B. Shader, Czech. Math. J. 48 (1998), 1-20.

  • W. So, Linear & Multilinear Algebra 46 (1999), 193-198.
  • R. B. Bapat, J. W. Grossman, and D. M. Kulkarni, Linear & Multilinear Algebra 46 (1999), 299-312.
  • O. Chan and B.- S. Ng, Linear Algebra Appl. 299 (1999), 175-190.
  • R. B. Bapat, Linear Algebra Appl. 302-303 (1999), 223-230.
  • O. Chan and T. K. Lam, SIAM J. Matrix Anal. Appl. 21 (1999), 129-144.
  • C.D. Godsil and I. Gutman, ACH-Models in Chem. 136 (1999), 503-510.
  • S. Kirkland, Czech. Math. J. 49 (1999), 617-632.
  • A. M. Duval and V. Reiner, Linear Algebra Appl. 294 (1999), 259-268.
  • R. B. Bapat, The Mathematics Student 68 (1999), 87-98.
  • J. Shah, Lect. Notes Comput. Sci. 1682 (1999), 129-140.

  • J. J. Molitierno, M. Neumann, and B. L. Shader, Electronic J. Linear Algebra 6 (2000), 62-71.
  • S. Kirkland, Linear & Multilinear Algebra 47 (2000), 93-103.
  • M. Petrovic, I. Gutman, M. Lepovic, and B. Milekic, Linear & Multilinear Algebra 47 (2000), 205-215.
  • R. B. Bapat, J. W. Grossman, and D. M. Kulkarni, Linear & Multilinear Algebra 47 (2000), 217-229.
  • D. Lorenzini, Linear & Multilinear Algebra 47 (2000), 281-306.
  • A. Berman and X.-D. Zhang, Linear & Multilinear Algebra 47 (2000), 307-311.
  • A. Berman and X.-D. Zhang, Linear Algebra Appl. 316 (2000), 13-20.
  • J. Shah, J. Visual Comm. & Image Rep. 11 (2000), 142-153.
  • S.C. Liu, L. D. Tong and Y.N. Yeh, Intl. J. Quantum Chem. 78 (2000), 331-140.
  • O. Rojo, R. Soto, and H. Rojo, Computers & Math. Appl. 39 (2000), 1-15.
  • J.-S. Li and Y.-L. Pan, Linear & Multilinear Algebra 48 (2000), 117-121.

  • Y.-L. Pan, J.-S. Li, and Y.-P. Hou, Linear & Multilinear Algebra 49 (2001), 209-218.
  • R. B. Bapat, S. J. Kirkland, and S. Pati, Linear & Multilinear Algebra 49 (2001), 219-242.
  • J.-S. Li and Y.-L. Pan, Linear Algebra Appl. 328 (2001), 153-160.
  • D. Stevanovic, Discrete Math. 235 (2001), 237-244.
  • S. Kirkland, Electronic J. Linear Algebra 8 (2001), 94-109.
  • D. A. Gregory, D. Hershkowitz, and S. J. Kirkland, Linear Algebra Appl. 332-334 (2001), 23-35.
  • S. Pati, Electronic J. Linear Algebra 8 (2001), 128-139.
  • M. Diudea, I. Gutman, and J. Lorentz, Molecular Topology, Nova Science Publishers, 2001 [p. 85]
  • A. A. Dobrynin, R. Entringer, and I. Gutman, Acta Applicandae Math 66 (2001), 211-249.
  • D. J. Klein and O. Ivanciuc, J. Math. Chem. 30 (2001), 271-287.
  • I. Gutman and D. Vidovic, J. Chem. Inf. Comp. Sci. 41 (2001), 1002-1005.

  • J. L. Shu, Y. Hong, and K. Wen-Pen, Linear Algebra Appl. 347 (2002), 123-129.
  • X. D. Zhang and J. S. Li, Linear Algebra Appl. 353 (2002), 11-20.
  • C. S. Oliveira, N. M. M. de Abreu, and S. Jurkiewicz, Linear Algebra Appl. 356 (2002), 113-121.
  • S. Kirkland and S. Pati, Linear & Multilinear Algebra 50 (2002), 253-284.
  • O. Rojo, Linear Algebra Appl. 349 (2002), 203-219.
  • S. M. Fallat, S. Kirkland, and S. Pati, Discrete Math 254 (2002), 115-142.
  • S. Friedland and R. Nabben, J. Graph Theory 41 (2002), 1-17.
  • I. Gutman and D. Vidovic, Indian J. Chem. A 41 (2002), 893-896.
  • I. Gutman, D. Vidovic, and D. Stevanovic, J. Serb. Chem. Soc. 67 (2002), 407-413.
  • G. Micheletti, G. Lattanzi, and A. Maritan, J. Molecular Biology 321 (2002), 909-921.
  • D. J. Klein, Croat. Chem. Acta 75 (2002), 633-649.
  • Xiao-Dong Zhang and R. Luo, Czech. J. Math. 52 (2002), 537-544.
  • A. M. Duval and V. Reiner, Trans. Amer. Math. Soc. 354 (2002), 4313-4344.
  • R. B. Ellis, III, PhD Dissertation, UC San Diego, 2002. [ .ps; .pdf]

  • D. Stevanovic, Linear Algebra Appl. 360 (2003), 35-42.
  • Y. Z. Fan and J. S. Li, Linear Algebra Appl. 360 (2003), 207-213.
  • J. J. Molitierno and M. Neumann, Linear Algebra Appl. 362 (2003), 75-85.
  • Xiao-Dong Zhang and R. Luo, Linear Algebra Appl. 362 (2003), 109-119.
  • J.-M. Guo, Linear Algebra Appl. 362 (2003), 121-128.
  • Y. P. Hou, J. S. Li, and Y. L. Pan, Linear & Multilinear Algebra 51 (2003), 21-30.
  • Y. L. Pan & Y. P. Hou, Linear & Multilinear Algebra 51 (2003), 31-38.
  • Y. Z. Fan, Linear & Multilinear Algebra 51 (2003), 147-154.
  • I. Gutman, MATCH-Commun. in Math. & Comput. Chem. 47 (2003), 133-140.
  • Y. Teranishi, Discrete Math. 260 (2003), 255-265.
  • F. Goldberg and G. Shapiro, Electronic J. Linear Algebra 10 (2003), 212-222.
  • J.-M. Guo, Linear Algebra Appl. 368 (2003), 379-385.
  • S. Kirkland, Linear Algebra Appl. 373 (2003), 5-11.
  • S. M. Fallat, S. Kirkland, and S. Pati, Linear Algebra Appl. 373 (2003), 31-50.
  • Yi-Zheng Fan, Linear Algebra Appl. 374 (2003), 307-316.
  • Xiao-Dong Zhang, European J. Combinatorics 24 (2003), 617-630.
  • S. M. Fallat, S. Kirkland, and S. Pati, Linear & Multilinear Algebra 51 (2003), 221-241.
  • I. Gutman, D. Vidovic, and B. Furtula, Indian J. Chem. Sect. A 42 (2003), 1272-1278.
  • W. J. Xiao and I. Gutman, Theor. Chem. Acc. 110 (2003), 284-289.
  • H. Z. Yang and G. Z. Hu, Sci. in China Ser. F - Inform. Sci. 46 (2003), 459-465.
  • R. B. Bapat, I. Gutman, and W. J. Xiao, Z. Naturforschung A 58 (2003), 494-498.
  • W. J. Xiao and I. Gutman, MATCH - Commun. in Math. & Comput. Chem. 49 (2003), 67-81.
  • I. Gutman, J. Serbian Chem. Soc. 68 (2003), 949-952.

  • Xiao-Dong Zheng, Linear Algebra Appl. 376 (2004), 207-213.
  • M. Petrovic, B. Borovicanin, and A. Torgasev, Linear Algebra Appl. 380 (2004), 173-184.
  • S. J. Kirkland and M. Neumann, Linear & Multilinear Algebra 52 (2004), 17-33.
  • S. J. Kirkland, Linear & Multilinear Algebra 52 (2004), 79-98.
  • J. J. Molitierno and M. Neumann, Linear & Multilinear Algebra 52 (2004), 145-156.
  • Xiao-Dong Zhang, Discrete Math. 278 (2004), 241-253.
  • Xiao-Dong Zhang, Linear Algebra Appl. 385 (2004), 369-379.
  • Xiao-Dong Zhang, Chinese Ann. Math. Ser. B 25 (2004), 103-110.
  • R. B. Bapat, MATCH - Commun. in Math. & Comput. Chem. 50 (2004), 73-82.
  • B. Zhou, Zeit. Naturforschung Sec. A-A 59 (2004), 181-184.
  • G. G. Cash and I. Gutman, MATCH-Comm. Math. & Comput. Chem. 51 (2004), 129-136.
  • X. B. Chen, Q. Y. Lin, and F. J. Zhang, Discrete Math. 282 (2004), 69-79.
  • B. Y. Wang and Y. N. Yeh, Intl. J. Quantum Chem 99 (2004), 80-91.
  • D. J. Klein, J. L. Palacios, M. Randic, and N. Trinajstic, J. Chem. Inf. & Comp. Sci. 44 (2004), 1521-1525.
  • J. A. Fax and R. M. Murray, IEEE Trans. Automatic Control 49 (2004), 1465-1476.
  • R. Olfati-Saber and R. M. Murray, Ibid, 1520-1533.
  • L. Xiao and S. Boyd, Systems & Control Lett. 53 (2004), 65-78.
  • Xiao-Dong Zhang, Ars Combinatoria 72 (2004), 191-198.
  • J.-S. Li and Y.-L. Pan, Acta Math. Sinica-English series 20 (2004), 803-806.
  • L. Grady and G. Funka-Lea, Lecture Notes in Comp. Sci. 3117 (2004), 230-245.

  • S. Barik and S. Pati, Linear Algebra Appl. 397 (2005), 209-222.
  • R. J. O'Callaghan and D. R. Bull, IEEE Trans. Image Processing 14 (2005), 49-62.
  • R. Agaev and P. Chebotarev, Linear Algebra Appl. 399 (2005), 157-168.
  • R. Bapat, S. J. Kirkland, and M. Neumann, Linear Algebra Appl. 401 (2005), 193-209.
  • Mei Lu, Huiqing Liu, and Feng Tian, Linear Algebra Appl. 402 (2005), 390-396.
  • O. Rojo and R. Soto, Linear Algebra Appl. 403 (2005), 97-117.

    • Also see U. Elsner's Graph Bisection Bibliography.