\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}

\begin{document}
\noindent
%
%
{\bf Cheng Yeaw Ku and Kok Bin Wong }
%
%

\medskip
\noindent
%
%
{\bf Maximum Multiplicity of Matching Polynomial Roots and Minimum Path Cover in General Graphs}
%
%

\vskip 5mm
\noindent
%
%
%
%
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.



\end{document}