Locating Eigenvalues of Perturbed Laplacian Matrices of Trees - Braga, Rodrigo Orsini; Rodrigues, Virgínia Maria (Trends in Computational and Applied Mathematics, 2018)
We give a linear time algorithm to compute the number of eigenvalues of any perturbed Laplacian matrix of a tree in a given real interval. The algorithm can be applied to weighted or unweighted trees. Using our method we characterize the trees that have up to $5$ distinct eigenvalues with respect to a family of perturbed Laplacian matrices that includes the adjacency and normalized Laplacian matrices as special cases, among others.