Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

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

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-25.