# zbMATH — the first resource for mathematics

Minimal edge-coverings of pairs of sets. (English) Zbl 0830.05051
The authors’ main result is a max-min theorem concerning bisupermodular functions on pairs of sets. Their result has a number of non-trivial consequences. It gives rise to a max-min formula for the minimum number of edges to be added to a digraph $$D$$ to make it $$k$$-node-connected and it implies a generalization of an edge-connectivity augmentation theorem of the first author; it also implies Mader’s theorem on splitting of edges in digraphs, Edmond’s theorem on matroid partitions, as well as an extension of Lubiw’s extension of Györi’s theorem on intervals.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05B35 Combinatorial aspects of matroids and geometric lattices 05C40 Connectivity 05C35 Extremal problems in graph theory 05C20 Directed graphs (digraphs), tournaments 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 05C38 Paths and cycles
Full Text: