\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
 
\def\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus
\def\pu{{\cal P}(u)}
\def\pv{{\cal P}(v)}
\def\puv{{\cal P}(u,v)}
\def\th{\theta}
\def\mtg{{\rm mult}(\th, G)}
\def\mt#1{{\rm mult}(\th, #1)}
\def\match{\mathop{\hbox{$\mu$}}\nolimits}
\def\mgx{\match(G,x)}
\def\mx#1{\match(#1,x)}
Abstract for C. D. Godsil, Algebraic Matching Theory

 
 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 $\mgx$ of $G$, and hence many results in matching theory
can be expressed in terms of this multiplicity.  Thus, if $\mtg$ denotes
the multiplicity of $\th$ as a zero of $\mgx$, then Gallai's lemma
is equivalent to the assertion that if $\mt{G\diff u}<\mtg$ for
each vertex $u$ of $G$, then $\mtg=1$.
 
This paper extends a number of results in matching theory to results
concerning $\mtg$, where $\th$ is not necessarily zero.  If $P$ is a
path in $G$ then $G\diff P$ denotes the graph got by deleting the
vertices of $P$ from $G$.  We prove that $\mt{G\diff P}\ge\mtg-1$, and
we say $P$ is {\sl $\th$-essential}\/ when equality holds.  We show
that if, all paths in $G$ are $\th$-essential, then $\mtg=1$.  We define
$G$ to be {\sl $\th$-critical}\/ if all vertices in $G$ are
$\th$-essential and $\mtg=1$.  We prove that if $\mtg=k$ then there is
an induced subgraph $H$ with exactly $k$ $\th$-critical components,
and the vertices in $G\diff H$ are covered by $k$ disjoint paths.
 

\bye

.
