Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.jctb.2009.05.001
Title: | An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomial | Authors: | Ku, C.Y. Chen, W. |
Keywords: | Gallai-Edmonds Structure Theorem Matching polynomial Vertex transitive graph |
Issue Date: | Mar-2010 | Citation: | Ku, C.Y., Chen, W. (2010-03). An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomial. Journal of Combinatorial Theory. Series B 100 (2) : 119-127. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jctb.2009.05.001 | 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. © 2009 Elsevier Inc. All rights reserved. | Source Title: | Journal of Combinatorial Theory. Series B | URI: | http://scholarbank.nus.edu.sg/handle/10635/102815 | ISSN: | 00958956 | DOI: | 10.1016/j.jctb.2009.05.001 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.