On packing connectors
type: Item
instance of: scholarly article
title: On packing connectors
zbMATH Open document ID: 0916.05056
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-03-08T00:00:00Z
review text: Let \(G=(V,E)\) be an undirected graph and \(\{S,T\}\) a partition of \(V\). Then a set of edges \(F\subseteq E\) such that every component of the subgraph \((V,F)\) intersects both \(S\) and \(T\), is called an \(S\)--\(T\) connector. In general a subpartition \(W\) of a set \(X\) is a collection of pairwise disjoint nonempty subsets of \(X\); and if---like in the present case---\(W=\{U_1, \dots, U_t\}\) is a subpartition of \(S\) or \(T\), then \(\delta(W)\) denotes the set of edges with one end in \(U_i\) and one end in \(V\setminus U_i\) for some index \(i\). The main result of this paper is Theorem 1: \(G\) contains \(k\) edge-disjoint \(S\)--\(T\) connectors iff \(|\delta (W)|\geq k\cdot | W|\) for every subpartition \(W\) of \(S\) or \(T\), where \(k\) is a natural number. This result is a generalization of a theorem on (i) disjoint edge covers in a bipartite graph (König/Gupta), and (ii) disjoint spanning trees in an undirected graph (Tutte/Nash-Williams), stated here as Lemma 1. According to the concept of \(S\)--\(T\) connector in undirected graphs the \(S\)--\(T\) bibranching is defined in directed graphs and a result of Schrijver with respect to packing bibranches is given as Lemma 2. The proof of Theorem 1 follows essentially by combining both these lemmas. Simultaneously this proof yields the basis for a polynomial algorithm for packing \(S\)--\(T\) connectors not described in the present paper. Finally, in Section 3, it is shown that Theorem 1 implies the integer rounding property for a set of linear inequalities associated with packing \(S\)--\(T\) connectors. The polyhedral formulation of this fact is given in Theorem 2.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1234269
zbMATH Keywords: partition
zbMATH Keywords: connector
zbMATH Keywords: packing bibranches
author: J. C. M. Keijsper
author: Alexander Schrijver
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: jctb.1998.1825
OpenAlex ID: W2165714486
cites work: Packing Spanning Trees
cites work: Q5580173
cites work: An efficient algorithm for minimum-weight bibranching
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Min-max Relations for Directed Graphs
cites work: Q3818127
cites work: On the Problem of Decomposing a Graph into n Connected Factors
cites work: Q4111952
DOI: 10.1006/JCTB.1998.1825
description: scientific article; zbMATH DE number 1234269