Packing the Steiner trees of a graph

Let G = ( V , E ) be an undirected graph with a distinguished set of terminal vertices K ⊆ V , | K | ≥ 2. A K ‐Steiner tree T of G is a tree containing the terminal vertex‐set K , where any vertex of degree one in T must belong to K . The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge‐disjoint K ‐Steiner trees, t K ( G ), contained in G . Specifically we are interested in finding a lower bound on t K ( G ) with respect to the K ‐edge‐connectivity, denoted as λ K ( G ). In 2003, Kriesell conjectured that any graph G with terminal vertex‐set K has at least ⌊λ K ( G )/2⌋ edge‐disjoint K ‐Steiner trees. In this article, we show that this conjecture can be answered affirmatively if the edges of G can be partitioned into K ‐Steiner trees. This result yields bounds for the problem of packing K ‐Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex‐set K , t K ( G ) ≥ ⌊λ K ( G )/2⌋ − | V − K |/2 − 1. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009