Tight bounds on the algebraic connectivity of Bethe trees (Q855576): Difference between revisions

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.