Authors: Joseph Henderson, Peter Seely, Benjamin Webb
Insitution: Brigham Young University
A classical result in spectral graph theory states that if a graph has an equitable partition then the eigenvalues of the associated divisor graph are a subset of the original graph’s eigenvalues. A natural question is whether it is possible to recover the remaining eigenvalues of the graph using this method of creating divisor graphs. We show that any weighted undirected graph can be decomposed into a number of subgraphs each with a nontrivial equitable partition whose collective spectra contain the remaining eigenvalues. We call these constructs Local Equitable Partitions (LEPs). We have developed an algorithm that leverages this result to compute LEPs and calculate the remaining eigenvalues of the original graph from them. This is potentially useful as many real-world data sets have a nontrivial equitable partition. To show the potential performance advantage of our algorithm over traditional methods, we present an ideal graph for which our algorithm performs optimally. Using a speed test, we demonstrate the improved temporal complexity of our method on the ideal graph.