On a conjecture involving Laplacian eigenvalues of trees

Abstract

Motivated by classic tree algorithms, in 1995 we designed a bottom-up $O(n)$ algorithm to compute the determinant of a tree's adjacency matrix $A$. In 2010 an $O(n)$ algorithm was found for constructing a diagonal matrix congruent to $A+x{I}_n$, $x\in \mathbb{R}$, enabling one to easily count the number of eigenvalues in any interval. A variation of the algorithm allows Laplacian eigenvalues in trees to be counted. We conjecture that for any tree $T$ of order $n\ge 2$, at least half of its Laplacian eigenvalues are less than $\bar{d}=2-\frac{2}{n}$, its average vertex degree.