Complete equitable decompositions.

A classical result in spectral graph theory states that if a graph G has an equitable partition π then the eigenvalues of the divisor graph G π are a subset of its eigenvalues, i.e. σ (G π) ⊆ σ (G). A natural question is whether it is possible to recover the remaining eigenvalues σ (G) − σ (G π) in a similar manner. Here we show that any weighted undirected graph with nontrivial equitable partition can be decomposed into a number of subgraphs whose collective spectra contain these remaining eigenvalues. Using this decomposition, which we refer to as a complete equitable decomposition, we introduce an algorithm for finding the eigenvalues of an undirected graph (symmetric matrix) with a nontrivial equitable partition. Under mild assumptions on this equitable partition we show that we can find eigenvalues of such a graph faster using this method when compared to standard methods. This is potentially useful as many real-world data sets are quite large and have a nontrivial equitable partition. [ABSTRACT FROM AUTHOR]