Improved Bounds for the Extremal Non-Trivial Laplacian Eigenvalues

Abstract

Let G be a simple connected graph and its Laplacian eigenvalues be µ1≥ µ2≥…≥ µn-1≥ µn=0. In this paper, we present an upper bound for the algebraic connectivity µn-1 of G and a lower bound for the largest eigenvalue µ1 of G in terms of the degree sequence d1,d2,…,dn of G and the number Ni∩Nj of common vertices of i and j (1≤i<j≤n) and hence we improve bounds of Maden and Büyükköse [14].

Keywords

• Laplacian eigenvalues
• upper bounds
• lower bounds
• eigenvalue inequalities.

References

1. Anderson W.N., Morley T.D., Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141-145.
2. Büyükköse Ş., Bounds for singular values using matrix traces, Msc Thesis, Selçuk University, (2000).
3. Chung F.R.K., Eigenvalues of Graphs, In Proceeding of the International Congress of Mathematician, 1333-1342. Switzerland, (1994)
4. Das K. Ch., An improved upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 368 (2003) 269-278.
5. Fiedler M., Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305.
6. Li J.-S., Zhang D., A new upper bound for eigenvalues of the Laplacian matrix of a graph, Linear Algebra Appl. 265 (1997) 93-100.
7. Li J.-S., Zhang D., On Laplacian eigenvalues of a graph, Linear Algebra Appl. 285 (1998) 305-307.
8. Lu M., Zhang L., Tian F., Lower bounds of the Laplacian spectrum of graphs based on diameter, Linear Algebra Appl. 420 (2007) 400-406.

9. Merris R., A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998) 33-35.
10. Merris R., Laplacian matrices of Graphs: a Survey, Linear Algebra and its Applications, 1 97, 198(1994) 143-176
11. Mohar B., The Laplacian spectrum of graphs, In Graph Theory, Combinatorics and Applications, Vol.2 (1998) 871-898.
12. Rojo O., Soto R., Rojo H., An always nontrivial upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 312(2000),155-159.
13. Wolkowicz H., Styan G.P.H., Bounds for eigenvalues using traces, Linear Algebra Appl. 29 (1980) 471-506.
14. Maden A.D., Büyükköse Ş., Bounds for Laplacian Graph Eigenvalues, Mathematical Inequalities and Applications, Vol 12, Num.3 (2012), 529-536.
15. Grone R., Merris R., The Laplacian spectrum of a graph, SIAM J. Discr. Math. 7 (1994) 221–229.
16. Li J.S., Pan Y.L., A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear Multilinear Algebra 48 (2000) 117–121.