A Conjecture on Laplacian Eigenvalues of Trees

DOI10.1007/978-3-319-97686-0_4zbMATH Open1414.05179arXiv1609.04579OpenAlexW2898413050MaRDI QIDQ5378296FDOQ5378296

David P. Jacobs, Vilmar Trevisan

Publication date: 12 June 2019

Published in: Graph Theory (Search for Journal in Brave)

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$, $xinmathbbR$, 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 $ngeq2$, at least half of its Laplacian eigenvalues are less than $$, its average vertex degree.

Full work available at URL: https://arxiv.org/abs/1609.04579

zbMATH Keywords

enumerationtree algorithms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Enumeration in graph theory (05C30)

Cited In (12)

• Title not available (Why is that?)
• A note on the integer eigenvalues of the Laplacian matrix of a balanced binary tree
• Minimizing the Laplacian eigenvalues for trees with given domination number
• Title not available (Why is that?)
• Most Laplacian eigenvalues of a tree are small
• Trees with 4 or 5 distinct normalized Laplacian eigenvalues
• On trees with Laplacian eigenvalue one
• Domination number and Laplacian eigenvalue of trees
• Title not available (Why is that?)
• Some remarks on the eigenvalue multiplicities of the Laplacian on infinite locally finite trees
• On the number of Laplacian eigenvalues of trees less than the average degree
• Trees with Four and Five Distinct Signless Laplacian Eigenvalues

This page was built for publication: A Conjecture on Laplacian Eigenvalues of Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5378296)