Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs (Q625411): Difference between revisions

Summary: 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.