Please use this identifier to cite or link to this item:
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.
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
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.


checked on Nov 26, 2022


checked on Nov 18, 2022

Page view(s)

checked on Nov 24, 2022

Google ScholarTM



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