Minmax results on edge-covers
by
Guoli Ding
LSU
Coauthors: Li Feng and Wenan Zang

An equivalent form of Konig's matching theorem is his covering theorem, which says that, in a bipartite graph with no isolated vertices, the edge-cover number equals the stable number. Our first result characterizes all graphs for which the weighted version of this minmax relation holds.

We also consider Gupta's theorem, the dual of Konig's convering theorem, which says that, in a bipartite graph, the maximum number of disjoint edge-covers equals the minimum degree of the graph. Our second result characterizes all graphs for which the weighted version of Gupta's minmax relation holds.

At the end of this talk, we discuss the problem of recognizing these graphs. As a result, we solve problems of Edmonds, Giles, and Schrijver on recognizing TDI systems, box-TDI systems, and integral polyhedra.

Date received: April 6, 2008