Extensions of barrier sets to nonzero roots of the matching polynomial

DOI10.1016/J.DISC.2010.09.002MaRDI QIDQ607015zbMATH OpenOpenAlexFDO

Authors Cheng Yeaw Ku, K. B. Wong

Publication date 19 November 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

barrier setsextreme setsGallai-Edmonds decompositionmatching polynomial

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(5)

• 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
• Properties of \(\theta\)-super positive graphs
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial

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)