Back to Search
Start Over
Packing of Steiner trees and S-connectors in graphs
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2012, Vol. 102 Issue 1, p186-205. 20p. - Publication Year :
- 2012
-
Abstract
- Abstract: Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G. We improve Lauʼs result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimiʼs criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 102
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 67345583
- Full Text :
- https://doi.org/10.1016/j.jctb.2011.06.003