Steiner tree packing number and tree connectivity.

Let S be a set of at least two vertices in a graph G . A subtree T of G is a S -Steiner tree if S ⊆ V ( T ) . Two S -Steiner trees T 1 and T 2 are edge-disjoint (resp. internally vertex-disjoint ) if E ( T 1 ) ∩ E ( T 2 ) = ∅ (resp. E ( T 1 ) ∩ E ( T 2 ) = ∅ and V ( T 1 ) ∩ V ( T 2 ) = S ). Let λ G ( S ) (resp. κ G ( S ) ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S -Steiner trees in G , and let λ k ( G ) (resp. κ k ( G ) ) be the minimum λ G ( S ) (resp. κ G ( S ) ) for S ranges over all k -subset of V ( G ) . Kriesell conjectured that if λ G ( { x , y } ) ≥ 2 k for any x , y ∈ S , then λ G ( S ) ≥ k . He proved that the conjecture holds for | S | = 3 , 4 . In this paper, we give a short proof of Kriesell’s Conjecture for | S | = 3 , 4 , and also show that λ k ( G ) ≥ 1 k − 1 k ℓ 2 (resp. κ k ( G ) ≥ 1 k − 1 k ℓ 2 ) if λ ( G ) ≥ ℓ (resp. κ ( G ) ≥ ℓ ) in G , where k = 3 , 4 . Moreover, we also study the relation between κ k ( L ( G ) ) and λ k ( G ) , where L ( G ) is the line graph of G . [ABSTRACT FROM AUTHOR]