Geodesic
Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/525
Classification : 05C31, 05C70
Mots-clés : \((\theta , G)\)-extremal path cover, Gallai-Edmonds Structure Theorem for general root 
@article{10_37236_525,
     author = {Cheng Yeaw Ku and Kok Bin Wong},
     title = {Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/525},
     zbl = {1229.05121},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/525/}
}
TY  - JOUR
AU  - Cheng Yeaw Ku
AU  - Kok Bin Wong
TI  - Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/525/
DO  - 10.37236/525
ID  - 10_37236_525
ER  - 
%0 Journal Article
%A Cheng Yeaw Ku
%A Kok Bin Wong
%T Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/525/
%R 10.37236/525
%F 10_37236_525
Cheng Yeaw Ku; Kok Bin Wong. Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/525

Cité par Sources :