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 μ(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 (Θ,G)-extremal path cover (where Θ is a root of μ(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.