Algebraic matching theory

C. D. Godsil

The electronic journal of combinatorics, Tome 2 (1995)

Résumé

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.

Détail

DOI : 10.37236/1202

Classification : 05D15, 05C70
Mots-clés : algebraic matching theory, matching, multiplicity, Gallai's lemma, path, \(\theta\)-essential, \(\theta\)-critical, induced subgraph