
doi: 10.37236/1202
The number of vertices missed by a maximum matching in a graph $G$ is the multiplicity of zero as a root of the matchings polynomial $\mu(G,x)$ of $G$, and hence many results in matching theory can be expressed in terms of this multiplicity. Thus, if $\mathrm{mult}(\theta,G)$ denotes the multiplicity of $\theta$ as a zero of $\mu(G,x)$, then Gallai's lemma is equivalent to the assertion that if $\mathrm{mult}(\theta,G\setminus u) < \mathrm{mult}(\theta,G)$ for each vertex $u$ of $G$, then $\mathrm{mult}(\theta,G)=1$. This paper extends a number of results in matching theory to results concerning $\mathrm{mult}(\theta,G)$, where $\theta$ is not necessarily zero. If $P$ is a path in $G$ then $G\setminus P$ denotes the graph got by deleting the vertices of $P$ from $G$. We prove that $\mathrm{mult}(\theta,G\setminus P)\ge\mathrm{mult}(\theta,G)-1$, and we say $P$ is $\theta$-essential when equality holds. We show that if, all paths in $G$ are $\theta$-essential, then $\mathrm{mult}(\theta,G)=1$. We define $G$ to be $\theta$-critical if all vertices in $G$ are $\theta$-essential and $\mathrm{mult}(\theta,G)=1$. We prove that if $\mathrm{mult}(\theta,G)=k$ then there is an induced subgraph $H$ with exactly $k$ $\theta$-critical components, and the vertices in $G\setminus H$ are covered by $k$ disjoint paths.
\(\theta\)-essential, algebraic matching theory, Transversal (matching) theory, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), matching, induced subgraph, multiplicity, path, Gallai's lemma, \(\theta\)-critical
\(\theta\)-essential, algebraic matching theory, Transversal (matching) theory, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), matching, induced subgraph, multiplicity, path, Gallai's lemma, \(\theta\)-critical
| 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). | 14 | |
| 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). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
