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

This paper deals with eigenvalues of a particular type of connected acyclic graphs: the Bethe trees. A Bethe tree \(B_{d,k}\) is a rooted unweighted tree of \(k\) levels in which the root vertex has degree equal to \(d\), the vertices at level \(j\) \((2 \leq j \leq k-1)\) have degree equal to \(d+1\) and the vertices at level \(k\) are the pendant vertices. In this paper, the authors obtain an explicit formula for the eigenvalues of the adjacency matrix of \(B_{d,k}\) and give the corresponding multiplicities. Specifically, the eigenvalues of the above-mentioned matrix are \[ 2\sqrt{d}\frac{\pi l}{j+1}, \;\;j=1,2,\dots,k, \;l=1,2,\dots,j, \] with multiplicity equal to \(d^{k-j-1}(d-1)\). The authors also derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of \(B_{d,k}\). Specifically, the numbers \[ d+1+2\sqrt{d}\cos{\frac{\pi j}{k}}, \;\;1 \leq j \leq k-1 \] are the simple nonzero eigenvalues of the Laplacian matrix of \(B_{d,k}\). Finally, the authors obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree \(\mathcal{T}\). These upper bounds are given in terms of the largest vertex degree \(\Delta\) and the radius of the tree \(\mathcal{T}\), \(\text{rad}(\mathcal{T})\). These bounds are attained if and only if \(\mathcal{T}\) is the Bethe tree \(B_{\Delta-1,\text{rad}{(\mathcal{T})}+1}\).