Tight bounds on the algebraic connectivity of Bethe trees

DOI10.1016/J.LAA.2006.03.016MaRDI QIDQ855576zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 7 December 2006

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2006.03.016

zbMATH Keywords

Laplacian matrixSherman-Morrison formula

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48)

Review text

Let \(G\) be a simple undirected graph on \(n\) vertices. Let \(D(G)\) denote the diagonal matrix of vertex degrees, \(A(G)\) denote the adjacency matrix of \(G\), and \(L(G)\) denote the Laplacian matrix of \(G\), \(D(G)-A(G)\). \(L(G)\) is known to be a positive semidefinite matrix, and its second smallest eigenvalue, \(a(G)\), is called the algebraic connectivity of \(G\) (according to a theorem of \textit{M. Fiedler} [Czech. Math. J. 23, 298--305 (1973; Zbl 0265.05119)] \(G\) is connected if and only \(a(G)>0\)). The paper calls a Bethe tree \(B_{d,k}\) a complete \(d\)-ary tree with root degree \(d\), which has \(k\) levels. The paper gives tight upper and lower bounds for the algebraic connectivity of the Bethe tree \(B_{d,k}\) and for that of two Bethe trees \(B_{d,k_1}\) and \(B_{d,k_2}\) joined at the root. The Sherman--Morrison formula is in use.

Recommendations

• Computing tight upper bounds on the algebraic connectivity of certain graphs
• Tight bounds on the algebraic connectivity of a balanced binary tree
• Spectra of copies of a generalized Bethe tree attached to any graph
• Ordering trees by algebraic connectivity
• Spectra of weighted generalized Bethe trees joined at the root

Cites work

• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• On the spectra of certain rooted trees
• The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
• Theory of monomer-dimer systems
• Tight bounds on the algebraic connectivity of a balanced binary tree

Cited in

(10)

• Perron value and moment of rooted trees
• On the spectrum of finite, rooted homogeneous trees
• Maximizing algebraic connectivity for certain families of graphs
• On a bound on algebraic connectivity: the case of equality
• Tight bounds on the algebraic connectivity of a balanced binary tree
• Line graph of combinations of generalized Bethe trees: Eigenvalues and energy
• Old and new results on algebraic connectivity of graphs
• Computing tight upper bounds on the algebraic connectivity of certain graphs
• Improved bounds for the Laplacian energy of Bethe trees
• A survey of automated conjectures in spectral graph theory

This page was built for publication: Tight bounds on the algebraic connectivity of Bethe trees

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