Strictly Interlaced Spectral Data for the Weighted Matching Polynomial of a Graph

Abstract

Interlacing of the real roots of a weighted matching polynomial for a graph $G$ and that of a vertex-deleted subgraph is classical and well-known. In the context of strict interlacing of distinct roots, a demonstrated graph construction gives rise to a new classification of graphs, called $\mathrm{SRSI}$ graphs, which include graphs that contain a Hamilton path. Graphs with a perfect (or nearly perfect) matching are shown to exhibit the SRSI${}_w(v)$ property with respect to a particular weighting and for specific vertices, and all such graphs are characterized via this graph construction. As a consequence, we also characterize the trees that possess the SRSI property for all edge weightings and all vertices.

16 pages, 7 figures