A note on the second largest eigenvalue of the Laplacian matrix of a graph. (English) Zbl 0979.15016

The Laplacian matrix of a connected simple graph \(G\) is defined as \(L(G)=D(G)-A(G)\) where \(A(G)\) is the adjacency matrix of \(G\) and \(D(G)=diag(d_1(G), \dots, d_n(G))\) is a diagonal matrix whose nonzero elements are the degrees of vertices of \(G\) and \(d_1(G) \geq d_2(G) \geq \dots \geq d_n(G)\). The Laplacian matrix \(L(G)\) is a singular positive semidefinite matrix with eigenvalues \(\lambda_1(G) \geq \lambda_2(G) \geq \dots \lambda_n(G)=0\).
The authors show that the second largest eigenvalue of the Laplacian matrix \(L(G)\) can be bounded using the second largest degree of \(G\), \(\lambda_2(G) \geq d_2(G)\). This lower bound is satisfied for any connected graph with \(n \geq 3\) vertices. They mention special cases when the equality is fulfilled.


15A42 Inequalities involving eigenvalues and eigenvectors
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C40 Connectivity
15B57 Hermitian, skew-Hermitian, and related matrices
Full Text: DOI


[1] DOI: 10.1080/03081088508817681 · Zbl 0594.05046
[2] DOI: 10.1137/S0895480191222653 · Zbl 0795.05092
[3] Horn, R. A. and Johnson, C. R. 1985.Matrix Analysis, 189–190. New York: Cambridge U.P.
[4] DOI: 10.1016/S0024-3795(98)10149-0 · Zbl 0931.05052
[5] DOI: 10.1016/S0024-3795(98)10148-9 · Zbl 0931.05053
[6] DOI: 10.1016/0024-3795(94)90486-3 · Zbl 0802.05053
[7] Mohar B., Graph Theory, Combinatorics and Applications pp 871– (1991)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.