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.

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: DOI