An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree

Abstract: A Bethe tree is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j have degree equal to and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of . Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of . Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree . These upper bounds are given in terms of the largest vertex degree and the radius of , and they are attained if and only if is a Bethe tree. [Copyright &y& Elsevier]