Abstract

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n k-j+1 and d k-j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are dj-1, 2 ≤ j ≤ k, while the diagonal entries are 0, ..., 0, ±1, in the case of the adjacency matrix, and d 1, d 2, ..., d k-1, d k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree. © 2005 Elsevier Inc. All rights reserved.