Premium
Node coverings with odd chains
Author(s) -
De Werra D.
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100206
Subject(s) - mathematics , bipartite graph , combinatorics , node (physics) , extension (predicate logic) , simple (philosophy) , link (geometry) , discrete mathematics , graph , computer science , philosophy , structural engineering , epistemology , engineering , programming language
A min‐max theorem for node coverings with odd chains in bipartite graphs is derived by simple network flow techniques. A characterization of minimum node covering in terms of a special kind of alternating chains is given, an extension of a result of Norman and Rabin on matchings and node coverings by edges is obtained.