Physical Sciences and Mathematics Commons^™

Tight Bounds On The Algebraic Connectivity Of A Balanced Binary Tree, Jason J. Molitierno, Michael Neumann, Bryan L. Shader

Mathematics Faculty Publications

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) + 0(1/2^2k).