On a conjecture involving Laplacian eigenvalues of trees

2016/09/15 by David P. Jacobs, Jacobs, David P., Vilmar Trevisan +1
Chemistry · Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.1609.04579

openalex publication_date 2016/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ∈ ℝ, 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 ≥ 2, at least half of its Laplacian eigenvalues are less than d = 2 - (2)/(n), its average vertex degree.

Citations

• Power and Centrality: A Family of Measures

Related

• Most Laplacian eigenvalues of a tree are small
• Trees with a large Laplacian eigenvalue multiplicity
• Tree simplification and the 'plateaux' phenomenon of graph Laplacian eigenvalues
• Laplacian eigenvalue distribution, diameter and domination number of trees
• Laplacian Spectrum and Domination in Trees