Generalizing Tutte's theorem and maximal non-matchable graphs

DOI10.1016/j.disc.2013.05.015zbMath1281.05108MaRDI QIDQ390291

Kok Bin Wong, Cheng Yeaw Ku

Publication date: 23 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2013.05.015

zbMATH Keywords

matching polynomial; Gallai-Edmonds decomposition; maximal non-matchable graphs; Tutte's theorem

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Extensions of barrier sets to nonzero roots of the matching polynomial, Gallai-Edmonds structure theorem for weighted matching polynomial

Cites Work

• Properties of \(\theta\)-super positive graphs
• Extensions of barrier sets to nonzero roots of the matching polynomial
• Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
• Matching theory
• Problems in algebraic combinatorics
• Algebraic matching theory
• Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover
• Gallai-Edmonds structure theorem for weighted matching polynomial
• Theory of monomer-dimer systems