Robert Grone and Russell Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7 (1994), 221-229. Research supported by the National Security Agency under grant no. MDA904-90-H-4024. Math Reviews 95d:05085.

This article is a continuation of publication 79: If G is a graph, its Laplacian matrix, L(G) = D(G) - A(G), is the difference of the diagonal matrix of its vertex degrees and its 0-1 adjacency matrix. The first section of this article is devoted to properties of Laplacian integral graphs, those for which the Laplacian spectrum consists entirely of integers. The second section relates the degree sequence and Laplacian spectrum through majorization. The third section introduces the notion of a d-cluster using it to obtain bounds on the multiplicity of d in the spectrum of L(G), overlapping the work of Isabel Faria [below].

The item in the article that has, perhaps, attracted the most attention is

Conjecture 2. If G is a connected graph, then the conjugate of its degree sequence majorizes its spectrum.

In a recent (still unpublished) paper, Tamon Stephen has confirmed the conjecture for a family that includes the regular graphs and the trees.

Among the publications citing this article are:

  • R. Grone, Linear & Multilinear Algebra 39 (1995), 133-136.
  • I. Faria, Linear Algebra Appl. 229 (1995), 15-35.
  • D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs, 3rd. ed., Johann Ambrosius Barth, Heidelberg, 1995.
  • D. Cvetkovic, P. Rowlinson, and S. Simic, Eigenspaces of Graphs, Encyclopedia of Mathematics and Its Applications 66, Cambridge University Press, 1997.
  • L. Halbeisen and N. Hungerbuhler, J. Graph Theory 31 (1999), 255-265.
  • W. So, Linear & Multilinear Algebra 46 (1999), 193-198.
  • J.-S. Li and Y.-L. Pan, Linear & Multilinear Algebra 48 (2000), 117-121.
  • L. Halbeisen and N. Hungerbuhler, European J. Combinatorics 21 (2000), 641-650.
  • H. Christianson and V. Reiner, Linear Algebra Appl. 349 (2002), 233-244.
  • A. M. Duval and V. Reiner, Trans. Amer. Math. Soc. 354 (2002), 4313-4344.
  • D. Stevanovic, Linear Algebra Appl. 360 (2003), 35-42.
  • X.-D. Zhang and R. Luo, Linear Algebra Appl. 362 (2003), 109-119.
  • 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.
  • Yi-Zheng Fan, Linear Algebra Appl. 374 (2003), 307-316.
  • W. J. Xiao and I. Gutman, Theor. Chem. Acc. 110 (2003), 284-289.
  • I. Gutman, J. Serbian Chem. Soc. 68 (2003), 949-952.
  • K. Ch. Das, Linear Algebra Appl. 376 (2004), 173-186.
  • Xiao-Dong Zhang, Linear Algebra Appl. 376 (2004), 207-213.
  • K. Ch. Das, Linear Algebra Appl. 384 (2004), 155-169.
  • Xiao-Dong Zhang, Linear Algebra Appl. 385 (2004), 369-379.
  • J.-S. Li and Y.-L. Pan, Acta Math. Sinica-English series 20 (2004), 803-806.
  • K. Ch. Das, Computers & Math. Appl. 48 (2004), 715-724.
  • R. J. O'Callaghan and D. R. Bull, IEEE Trans. Image Processing 14 (2005), 49-62.
  • Y. Teranishi, Discrete Math. 290 (2005), 259-267.
  • R. Agaev and P. Chebotarev, Linear Algebra Appl. 399 (2005), 157-168.
  • Mei Lu, Huiqing Liu, and Feng Tian, Linear Algebra Appl. 402 (2005), 390-396.
  • S. Kirkland, Discrete Math. 295 (2005), 75-90.