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

Li, Jiong-Sheng; Pan, Yong-Liang

Linear Multilinear Algebra 48, No. 2, 117-121 (2000).

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.

Reviewer: Jitka Drkošova (Praha)

MSC:

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

Keywords:

connected simple graph; Laplacian matrix; second largest eigenvalue; adjacency matrix; lower bound

References:

[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)