%0 Journal Article %1 godsil12 %A Godsil, Chris D. %D 2012 %K gallai-edmonds graph.theory matching polynomial %T Algebraic Matching Theory %U http://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r8 %X 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 $mult(þeta,G)$ denotes the multiplicity of $þeta$ as a zero of $\mu(G,x)$, then Gallai's lemma is equivalent to the assertion that if $mult(þeta,Gu) This paper extends a number of results in matching theory to results concerning $mult(þeta,G)$, where $þeta$ is not necessarily zero. If $P$ is a path in $G$ then $GP$ denotes the graph got by deleting the vertices of $P$ from $G$. We prove that $mult(þeta,GP)\gemult(þeta,G)-1$, and we say $P$ is $þeta$-essential when equality holds. We show that if, all paths in $G$ are $þeta$-essential, then $mult(þeta,G)=1$. We define $G$ to be $þeta$-critical if all vertices in $G$ are $þeta$-essential and $mult(þeta,G)=1$. We prove that if $mult(þeta,G)=k$ then there is an induced subgraph $H$ with exactly $k$ $þeta$-critical components, and the vertices in $GH$ are covered by $k$ disjoint paths.

@article{godsil12, abstract = { 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) 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. }, added-at = {2017-03-28T12:47:30.000+0200}, author = {Godsil, Chris D.}, biburl = {https://www.bibsonomy.org/bibtex/29727e2fe943e8e5202600564fdaff11c/ytyoun}, description = {Algebraic Matching Theory | Godsil | The Electronic Journal of Combinatorics}, interhash = {ae7b8c668239c544a4e09bb98eea3933}, intrahash = {9727e2fe943e8e5202600564fdaff11c}, keywords = {gallai-edmonds graph.theory matching polynomial}, timestamp = {2017-03-29T08:11:40.000+0200}, title = {Algebraic Matching Theory}, url = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r8}, year = 2012 }