Edge-Matching Graph Contractions and their Interlacing Properties

Abstract

For a given graph $\mathcal{G}$ of order $n$ with $m$ edges, and a real symmetric matrix associated to the graph, $M\left(\mathcal{G}\right)\in {\mathbb{R}}^{n\times n}$, the interlacing graph reduction problem is to find a graph ${\mathcal{G}}_r$ of order $r<n$ such that the eigenvalues of $M\left({\mathcal{G}}_r\right)$ interlace the eigenvalues of $M\left(\mathcal{G}\right)$. Graph contractions over partitions of the vertices are widely used as a combinatorial graph reduction tool. In this study, we derive a graph reduction interlacing theorem based on subspace mappings and the minmax theory. We then define a class of edge-matching graph contractions and show how two types of edge-matching contractions provide Laplacian and normalized Laplacian interlacing. An $\mathcal{O}\left(mn\right)$ algorithm is provided for finding a normalized Laplacian interlacing contraction and an $\mathcal{O}\left(n^2+nm\right)$ algorithm is provided for finding a Laplacian interlacing contraction.