Tight bounds on the algebraic connectivity of Bethe trees

A rooted Bethe tree Bd,k is an unweighted rooted tree of k levels in which the vertex root has degree d, the vertices in level 2 to level (k − 1) have degree (d + 1) and the vertices in level k have degree 1 (pendant vertices). In this paper, we derive tight upper and lower bounds on the algebraic connectivity of(1)a Bethe tree Bd,k, and(2)a tree Bd,k1,k2 obtained by the union of two Bethe trees Bd,k1 and Bd,k2 having in common the vertex root.A useful tool in our study is the Sherman–Morrison formula.