pith. sign in

arxiv: 1609.04579 · v2 · pith:SLL3UIKZnew · submitted 2016-09-15 · 🧮 math.CO

On a conjecture involving Laplacian eigenvalues of trees

classification 🧮 math.CO
keywords eigenvaluesalgorithmlaplaciantreeconjecturematrixtreesadjacency
0
0 comments X
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.