ELA, Volume 6, pp. 62-71, March 2000, abstract.
Tight Bounds on the Algebraic Connectivity
of a Balanced Binary Tree
Jason J. Molitierno, Michael Neumann, and Bryan L. Shader
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^k-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^k-2k+3)+ O(1/2^{2k}).