
doi: 10.37236/525
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.
Graph polynomials, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Gallai-Edmonds Structure Theorem for general root, \((\theta , G)\)-extremal path cover, 004, 510
Graph polynomials, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Gallai-Edmonds Structure Theorem for general root, \((\theta , G)\)-extremal path cover, 004, 510
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
