König-Egerváry Graphs are Non-Edmonds

Research output: Contribution to journalArticlepeer-review

Abstract

König-Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125-130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors ∈ ℝE satisfying two families of constraints: 'vertex saturation' and 'blossom'. Graphs for which the latter constraints are implied by the former are termed non-Edmonds. This note presents two proofs-one combinatorial, one algorithmic-of its title's assertion. Neither proof relies on the characterization of non-Edmonds graphs due to de Carvalho et al. (J Combin Theory Ser B 92:319-324, 2004).

Original languageEnglish
Pages (from-to)721-726
Number of pages6
JournalGraphs and Combinatorics
Volume26
Issue number5
DOIs
StatePublished - Sep 2010

Keywords

  • Covering
  • Matching
  • Perfect matching polytope

Fingerprint

Dive into the research topics of 'König-Egerváry Graphs are Non-Edmonds'. Together they form a unique fingerprint.

Cite this