R. Merris, The number of eigenvalues greater than 2 in the Laplacian spectrum of a graph, Portugaliae Math. 48 (1991), 245-349. Math Reviews 92h:05088.

Denoted L(G), the Laplacian matrix of graph G is the difference of the diagonal matrix of its vertex degrees and its adjacency matrix. So, L(G) is a positive semidefinite, symmetric, singular, M-matrix. Denote the eigenvalues of L(G) by l1(G) >= l2(G) >= ... >= ln(G). If n = 2k and if G is hamiltonian, then lk(G) >= 2, motivating interest in bounds on the number of Laplacian eigenvalues (multiplicities included) not less than 2.

A pendant vertex is a vertex of degree 1, and a pendant neighbor is a vertex adjacent to a pendant vertex. Denote by m(I) the number of eigenvalues of L(G) (multiplicities included) that lie in the interval I. Let G be a connected graph on n > 2 vertices, having q pendant neighbors. If n = 2q, then m[0,1) = q, m[1,2) = 0, and m(2) = 1. If n > 2q, then at least q eigenvalues of L(G) (multiplicities included) are greater than 2. In particular, the number of eigenvalues greater than 2 is less than q if and only if the pendant edges of G comprise a perfect matching. Finally, the number of eigenvalues of L(G) greater than 2 is not less than half the length of a longest path in G.

Among the publications citing this article are:

  • R. Grone, Linear Algebra Appl. 150 (1991), 167-178.
  • D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs, 3rd ed., Johann Ambrosius Barth Verlag, Heidelberg, 1995.
  • M. Petrovic, I. Gutman, M. Lepovic and B. Milekic, Linear & Multilinear Algebra 47 (2000), 205-215.
  • G. J. Ming and T. S. Wang, Linear Algebra Appl. 325 (2001), 71-74.
  • Y. Z. Fan and J. S. Li, Linear Algebra Appl. 360 (2003), 207-213.
  • Xiao-Dong Zhang, European J. Combinatorics 24 (2003), 617-630.
  • M. Petrovic, B. Borovicanin, and A. Torgasev, Linear Algebra Appl. 380 (2004), 173-184.
  • Xiao-Dong Zhang, Discrete Math. 278 (2004), 241-253.
  • Xiao-Dong Zhang, Chinese Ann. Math. Ser. B 25 (2004), 103-110.