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

P. Mark Kayll

doi:10.1007/s00373-010-0940-y

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

P. Mark Kayll

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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 language	English
Pages (from-to)	721-726
Number of pages	6
Journal	Graphs and Combinatorics
Volume	26
Issue number	5
DOIs	https://doi.org/10.1007/s00373-010-0940-y
State	Published - Sep 2010

Keywords

Covering
Matching
Perfect matching polytope

Access to Document

10.1007/s00373-010-0940-y

Cite this

@article{5559b579b86247c0adc5f00c81b6dcd8,

title = "K{\"o}nig-Egerv{\'a}ry Graphs are Non-Edmonds",

abstract = "K{\"o}nig-Egerv{\'a}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).",

keywords = "Covering, Matching, Perfect matching polytope",

author = "{Mark Kayll}, P.",

year = "2010",

month = sep,

doi = "10.1007/s00373-010-0940-y",

language = "English",

volume = "26",

pages = "721--726",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "5",

}

TY - JOUR

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

AU - Mark Kayll, P.

PY - 2010/9

Y1 - 2010/9

N2 - 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).

AB - 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).

KW - Covering

KW - Matching

KW - Perfect matching polytope

UR - http://www.scopus.com/inward/record.url?scp=78049528362&partnerID=8YFLogxK

U2 - 10.1007/s00373-010-0940-y

DO - 10.1007/s00373-010-0940-y

M3 - Article

AN - SCOPUS:78049528362

SN - 0911-0119

VL - 26

SP - 721

EP - 726

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 5

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this