Locating Eigenvalues of Perturbed Laplacian Matrices of Trees

Rodrigo Orsini Braga, Virgínia Maria Rodrigues


We give a linear time algorithm to compute the number of eigenvalues of any perturbedLaplacian matrix of a tree in a given real interval. The algorithm can be applied to weightedor unweighted trees. Using our method we characterize the trees that have up to $5$ distincteigenvalues with respect to a family of perturbed Laplacian matrices that includes the adjacencyand normalized Laplacian matrices as special cases, among others.


Perturbed Laplacian matrix, eigenvalue location, trees

Full Text:



R.B. Bapat, S. J. Kirkland, S. Pati, The perturbed Laplacian matrix of a graph, {em Linear and Multilinear Algebra}, {bf 49} (2001), 219--242.

A.E. Brouwer, W.H. Haemers, ``Spectra of graphs'', Springer, New York, 2012.

R.O. Braga, R.R. Del-Vecchio, V.M. Rodrigues, V. Trevisan, Trees with 4 or 5 distinct normalized Laplacian eigenvalues, {em Linear Algebra and its Applications}, {bf 471} (2015), 615--635.

F.R.K. Chung, ``Spectral Graph Theory'', American Math. Soc., Providence, 1997.

E. Fritscher, C. Hoppen, I. Rocha, V. Trevisan, On the sum of the Laplacian eigenvalues of a tree, {em Linear Algebra and its Applications}, {bf 435} (2011), 371--399.

R. Horn, C.R. Johnson, ``Matrix Analysis'', Cambridge University Press, 1985.

D.P. Jacobs, V. Trevisan, Locating the eigenvalues of trees, {em Linear Algebra and its Applications}, {bf 434} (2011), 81--88.

S. Radenkovi'{c}, I. Gutman, Total $pi$-electron energy and Laplacian

energy: how far the analogy goes?, {em Journal of the Serbian Chemical Society}, {bf 73} (2007), 1343--1350.

DOI: https://doi.org/10.5540/tema.2017.018.03.479

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM


  • There are currently no refbacks.

Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)


Indexed in:




Desenvolvido por:

Logomarca da Lepidus Tecnologia