Minimal edge-coverings of pairs of sets
type: Item
instance of: scholarly article
title: Minimal edge-coverings of pairs of sets
zbMATH Open document ID: 0830.05051
author: András Frank
author: Tibor Jordán
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-09-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 798758
zbMATH Keywords: edge-coverings
zbMATH Keywords: max-min theorem
zbMATH Keywords: digraph
zbMATH Keywords: edge-connectivity augmentation theorem
reviewed by: J. W. Moon
MaRDI profile type: Publication
OpenAlex ID: W1988132050
DOI: 10.1006/JCTB.1995.1044
description: scientific article; zbMATH DE number 798758