Article ID Journal Published Year Pages File Type
4656726 Journal of Combinatorial Theory, Series B 2016 36 Pages PDF
Abstract

Let T be a distinguished subset of vertices in a graph G. A T-Steiner tree is a subgraph of G that is a tree and that spans T. Kriesell conjectured that G contains k pairwise edge-disjoint T-Steiner trees provided that every edge-cut of G that separates T   has size ≥2k≥2k. When T=V(G)T=V(G) a T-Steiner tree is a spanning tree and the conjecture is a consequence of a classic theorem due to Nash-Williams and Tutte. Lau proved that Kriesell's conjecture holds when 2k is replaced by 24k, and recently West and Wu have lowered this value to 6.5k  . Our main result makes a further improvement to 5k+45k+4.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,