Please use this identifier to cite or link to this item:
|Title:||An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomial||Authors:||Ku, C.Y.
|Keywords:||Gallai-Edmonds Structure Theorem
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.