Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.disc.2013.05.015
Title: Generalizing Tutte's theorem and maximal non-matchable graphs
Authors: Ku, C.Y. 
Wong, K.B.
Keywords: Gallai-Edmonds decomposition
Matching polynomial
Maximal non-matchable graphs
Tutte's theorem
Issue Date: 2013
Citation: Ku, C.Y., Wong, K.B. (2013). Generalizing Tutte's theorem and maximal non-matchable graphs. Discrete Mathematics 313 (20) : 2162-2167. ScholarBank@NUS Repository. https://doi.org/10.1016/j.disc.2013.05.015
Abstract: A graph G has a perfect matching if and only if 0 is not a root of its matching polynomial μ(G, x). Thus, Tutte's famous theorem asserts that 0 is not a root of μ(G, x) if and only if codd(G - S) ≤ |S| for all S ⊆ V(G), where codd(G) denotes the number of odd components of G. Tutte's theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte's theorem in terms of avoiding any given real number Θ as a root of μ(G, x). We also extend maximal nonmatchable graphs to maximal Θ-non-matchable graphs and determine the structure of such graphs. © 2013 Elsevier B.V. All rights reserved.
Source Title: Discrete Mathematics
URI: http://scholarbank.nus.edu.sg/handle/10635/103336
ISSN: 0012365X
DOI: 10.1016/j.disc.2013.05.015
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Apr 3, 2020

WEB OF SCIENCETM
Citations

1
checked on Mar 18, 2020

Page view(s)

37
checked on Mar 28, 2020

Google ScholarTM

Check

Altmetric


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