Improved Bounds for the Extremal non-trivial Laplacian Eigenvalues

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

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.

Full Text:

PDF

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.