Tight bounds on the algebraic connectivity of Bethe trees
type: Item
instance of: scholarly article
title: Tight bounds on the algebraic connectivity of Bethe trees
zbMATH Open document ID: 1107.05026
author: N. E. Zubov
published in: Linear Algebra and its Applications
publication date: 2006-12-07T00:00:00Z
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.
reviewed by: László A. Székely
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15B48
zbMATH DE Number: 5078016
zbMATH Keywords: Laplacian matrix
zbMATH Keywords: Sherman-Morrison formula
MaRDI profile type: Publication
full work available at URL: j.laa.2006.03.016
OpenAlex ID: W2078438273
cites work: Q5682350
cites work: Q3359644
cites work: Theory of monomer-dimer systems
cites work: Q4040931
cites work: Tight bounds on the algebraic connectivity of a balanced binary tree
cites work: The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
cites work: On the spectra of certain rooted trees
DOI: 10.1016/J.LAA.2006.03.016
description: scientific article; zbMATH DE number 5078016