Extensions of barrier sets to nonzero roots of the matching polynomial

DOI10.1016/J.DISC.2010.09.002zbMATH Open1200.05109arXiv0909.5249OpenAlexW2014552601MaRDI QIDQ607015FDOQ607015

Authors: Cheng Yeaw Ku, K. B. Wong 

Publication date: 19 November 2010

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

Abstract: In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to its connection to maximum matchings in a graph. In this paper, we first define $heta$-barrier sets. Our definition of a $heta$-barrier set is slightly different from that of a barrier set. However we show that $heta$-barrier sets and barrier sets have similar properties. In particular, we prove a generalized Berge's Formula and give a characterization for the set of all $heta$-special vertices in a graph.

Full work available at URL: https://arxiv.org/abs/0909.5249

Recommendations

• Generalizing Tutte's theorem and maximal non-matchable graphs
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• Algebraic matching theory
• Disclosing barriers: a generalization of the canonical partition based on Lovász's formulation
• The extreme set condition of a graph

zbMATH Keywords

matching polynomialextreme setsGallai-Edmonds decompositionbarrier sets

Mathematics Subject Classification ID

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

Cites Work

• Matching theory
• Problems in algebraic combinatorics
• On the theory of the matching polynomial
• Algebraic matching theory
• An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
• Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover
• Generalizing Tutte's theorem and maximal non-matchable graphs
• Properties of \(\theta\)-super positive graphs
• Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial

Cited In (4)

• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• A refined Gallai-Edmonds structure theorem for weighted matching polynomials
• Gallai-Edmonds structure theorem for weighted matching polynomial
• Generalizing Tutte's theorem and maximal non-matchable graphs

This page was built for publication: Extensions of barrier sets to nonzero roots of the matching polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607015)