Published March 2010
| public
Journal Article
An analogue of the Gallai–Edmonds Structure Theorem for non-zero roots of the matching polynomial
- Creators
- Ku, Cheng Yeaw
- Chen, William
Abstract
Godsil observed the simple fact that the multiplicity of 0 as a root of the matching polynomial of a graph coincides with the classical notion of deficiency. From this fact he asked to what extent classical results in matching theory generalize, replacing "deficiency" with multiplicity of θ as a root of the matching polynomial. We prove an analogue of the Stability Lemma for any given root, which describes how the matching structure of a graph changes upon deletion of a single vertex. An analogue of Gallai's Lemma follows. Together these two results imply an analogue of the Gallai–Edmonds Structure Theorem. Consequently, the matching polynomial of a vertex transitive graph has simple roots.
Additional Information
© 2009 Elsevier Inc. Received 30 June 2008. Available online 23 May 2009. We would like to thank the anonymous referee for the comments that helped us make several improvements to this paper.Additional details
- Eprint ID
- 17900
- DOI
- 10.1016/j.jctb.2009.05.001
- Resolver ID
- CaltechAUTHORS:20100408-101925522
- Created
-
2010-04-21Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field