##
EIGENVALUE LOCATION OF SYMMETRIC MATRICES

VILMAR TREVISAN

We address the problem of estimating graph eigenvalues in terms of eigenvalue
location, by which we mean determining the number of eigenvalues of a symmetric
matrix that lie in any given real interval.

Our algorithms are based on diagonalizing matrices and rely on Sylvesterâ€™s Law of
Inertia. They are either designed for graphs in a particular class, and exploit some
special feature of this class, or they rely on a structural decomposition of the input
graph.

We show how a simple linear-time tree algorithm can be extended to symmetric
matrices whose underlying graph has a tree decomposition of small width. We also
describe how a linear-time cograph algorithm can be extended to matrices whose
underlying graph has small clique-width.

These algorithms have applications that go beyond estimating eigenvalues of a
particular graph, and allow us to obtain properties of an entire class. We illustrate
this with applications to the solution of relevant problems in Spectral Graph
Theory.

UFRGS-Universidae Federal do Rio Grande do Sul

Email address: trevisan@mat.ufrgs.br