Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees

DOI10.1016/J.DISC.2005.04.001MaRDI QIDQ2487982zbMATH OpenOpenAlexFDO

Authors Yuan Hong, Xiao-Dong Zhang

Publication date 17 August 2005

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.04.001

zbMATH Keywords

Laplacian eigenvalue pendant vertex

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Review text

The paper presents some lower and upper bounds for the Laplacian spectral radius of trees depending only on the degree sequences. Let be given a simple directed graph \(G\) with a vertex set \(\{v_1,\dots,v_n\}\). Its \(n\times n\) dimensional Laplacian matrix is \(L(G)=D(G)-A(G)\) with \(D(G)= \text{diag} (d_1,\dots,d_n)\), where \(d_i\) is the degree of \(v_i\). \(A(G)\) denotes the adjacency matrix of \(G\). Denote the eigenvalues of \(L(G)\) in non-increasing order as \(\mu (G)=\mu_1(G)\geq\dots \geq\mu_n(G)=0\). \(\mu (G)\) is called the Laplacian spectrum radius of \(G\). A pendant vertex of \(G\) is a vertex of degree one. A tree \(T_{n,k}\) with \(n\) vertices is obtained from a star \(K_{1,k}\) and \(k\) paths of almost equal lengths by joining each pendant vertex of \(K_{1,k}\) to an end vertex of one path. The results are as follows: (1) Let \(T\) be a tree with \(n\) vertices and \(k\) pendant vertices. Then \(\mu (T)\leq\mu (T_{n,k})\). Equality holds if and only if \(T\) is isomorphic to \(T_{n,k}\). (2) Let \(G\) be a simple connected bipartite graph with degrees \(d_1,\dots,d_n\). Then \(\mu (G)\geq 2\sqrt{{1\over{n}}\sum_{i=1}^nd_i^2}\). Equality holds if and only if \(G\) is a regular connected bipartite graph. (3) Let \(G\) be a simple connected bipartite graph with vertices \(v_1,\dots, v_n\) and their degrees \(d_1,\dots,d_n\). Then \(\mu (G)\geq 2+\sqrt{{1\over{m}}\sum_{v_i\sim v_j,i<j}(d_i+d_j-2)^2}\). \(m\) is the number of edges. Equality holds if and only if \(G\) is either a regular connected bipartite graph or a semi-regular bipartite graph or the path with four vertices.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2487982)