Eigenvalue location in graphs of small clique-width

Abstract

Finding a diagonal matrix congruent to $A-cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(\text{poly}(k)n)$ where $n$ is the order of $G$.

25 pages