Paper Info
Title
König–Egerváry Graphs are Non-Edmonds
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 $${{\bf{x}}\in\mathbb R^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).
Year
DOI
Venue
2010
10.1007/s00373-010-0940-y
Graphs and Combinatorics
Keywords
DocType
Volume
minimum-order covering,matching · perfect matching polytope · covering,maximum matchings,non-edmonds graph,latter constraint,nonnegative vector,j combin theory ser,graph g,standards sect b,ry graphs,mathbb r,j res nat bur
Journal
26
Issue
ISSN
Citations 
5
1435-5914
3
PageRank 
References 
Authors
0.44
3
1
Name
Order
Citations
PageRank
P. Mark Kayll1658.34