Locating Eigenvalues of Perturbed Laplacian Matrices of Trees

Authors

DOI:

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

Keywords:

Perturbed Laplacian matrix, eigenvalue location, trees

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.

Author Biography

Rodrigo Orsini Braga, Universidade Federal do Rio Grande do Sul

Doutor em Matemática Aplicada (UFRGS, 2015)

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.

Downloads

Published

2018-01-10

How to Cite

Braga, R. O., & Rodrigues, V. M. (2018). Locating Eigenvalues of Perturbed Laplacian Matrices of Trees. Trends in Computational and Applied Mathematics, 18(3), 479. https://doi.org/10.5540/tema.2017.018.03.479

Issue

Section

Original Article