Locating Eigenvalues of Perturbed Laplacian Matrices of Trees

Rodrigo Orsini Braga, Virgínia Maria Rodrigues

Abstract


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.

Keywords


Perturbed Laplacian matrix, eigenvalue location, trees

Full Text:

PDF

References


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

Refbacks

  • 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