Locating eigenvalues of perturbed laplacian matrices of trees

Abstract

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.

Nós apresentamos um algoritmo de tempo linear para calcular o número de autovalores de uma matriz laplaciana perturbada qualquer associada a uma árvore, num dado intervalo real. Este algoritmo pode ser aplicado a árvores com ou sem pesos. Utilizando este procedimento, obtemos uma caracterização das árvores com até cinco autovalores distintos para uma família de matrizes laplacianas perturbadas, que inclui a matriz de adjacências e a matriz laplaciana normalizada como casos particulares, entre outras.