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
Source: 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.

SCOPUSTM   
Citations

9
checked on Feb 22, 2018

WEB OF SCIENCETM
Citations

4
checked on Jan 22, 2018

Page view(s)

24
checked on Feb 19, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.