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.
Maximal non-matchable graphs
|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.
checked on Apr 3, 2020
WEB OF SCIENCETM
checked on Mar 18, 2020
checked on Mar 28, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.