On a conjecture involving Laplacian eigenvalues of trees
classification
🧮 math.CO
keywords
eigenvaluesalgorithmlaplaciantreeconjecturematrixtreesadjacency
read the original 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 + xI_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 \geq 2$, at least half of its Laplacian eigenvalues are less than $\bar{d} = 2 - \frac{2}{n}$, its average vertex degree.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.