Improved Bounds for the Extremal Non-Trivial Laplacian Eigenvalues

Year 2015, Volume: 28 Issue: 1, 65 - 68, 23.02.2015

Şerife Büyükköse , Ercan Altınışık Feyza Yalçın

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

• Anderson W.N., Morley T.D., Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141-145.
• Büyükköse Ş., Bounds for singular values using matrix traces, Msc Thesis, Selçuk University, (2000).
• Chung F.R.K., Eigenvalues of Graphs, In Proceeding of the International Congress of Mathematician, 1333-1342. Switzerland, (1994)
• Das K. Ch., An improved upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 368 (2003) 269-278.
• Fiedler M., Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305.
• 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.
• Li J.-S., Zhang D., On Laplacian eigenvalues of a graph, Linear Algebra Appl. 285 (1998) 305-307.
• Lu M., Zhang L., Tian F., Lower bounds of the Laplacian spectrum of graphs based on diameter, Linear Algebra Appl. 420 (2007) 400-406.
• Merris R., A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998) 33-35.
• Merris R., Laplacian matrices of Graphs: a Survey, Linear Algebra and its Applications, 1 97, 198(1994) 143-176
• Mohar B., The Laplacian spectrum of graphs, In Graph Theory, Combinatorics and Applications, Vol.2 (1998) 871-898.
• Rojo O., Soto R., Rojo H., An always nontrivial upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 312(2000),155-159.
• Wolkowicz H., Styan G.P.H., Bounds for eigenvalues using traces, Linear Algebra Appl. 29 (1980) 471-506.
• Maden A.D., Büyükköse Ş., Bounds for Laplacian Graph Eigenvalues, Mathematical Inequalities and Applications, Vol 12, Num.3 (2012), 529-536.
• Grone R., Merris R., The Laplacian spectrum of a graph, SIAM J. Discr. Math. 7 (1994) 221–229.
• 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.