Maximum Multiplicity of Matching Polynomial Roots and Minimum Path Cover in General Graphs

Abstract

Let $G$ be a graph. It is well known that the maximum multiplicity of a root of the matching polynomial $\mu(G,x)$ is at most the minimum number of vertex disjoint paths needed to cover the vertex set of $G$. Recently, a necessary and sufficient condition for which this bound is tight was found for trees. In this paper, a similar structural characterization is proved for any graph. To accomplish this, we extend the notion of a $(\theta,G)$-extremal path cover (where $\theta$ is a root of $\mu(G,x)$) which was first introduced for trees to general graphs. Our proof makes use of the analogue of the Gallai-Edmonds Structure Theorem for general root. By way of contrast, we also show that the difference between the minimum size of a path cover and the maximum multiplicity of matching polynomial roots can be arbitrarily large.