Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:the generalized Bethe tree B,a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,a graph obtained from the cycle Cr by attaching B, by its root, to each vertex of the cycle, anda tree obtained from the path Pr by attaching B, by its root, to each vertex of the path,is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.