Tight bounds on the algebraic connectivity of a balanced binary tree

Abstract

In this paper, quite tight lower and upper bounds are obtained on the algebraic connectivity, namely, the second-smallest eigenvalue of the Laplacian matrix, of an unweighted balanced binary tree with k levels and hence n = 2 1 vertices. This is accomplished by considering the inverse of a matrix of order k 1 readily obtained from the Laplacian matrix. It is shown that the algebraic connectivity is 1=(2 2k + 3) +O(1=2).