Abstract

A Bethe tree B d,k is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j (2 ≤ j ≤ k - 1) have degree equal to (d + 1) 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 B d,k. 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 B d,k. Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree J. These upper bounds are given in terms of the largest vertex degree and the radius of J, and they are attained if and only if J is a Bethe tree. © 2007 Elsevier Inc. All rights reserved.