Rainbow trees in graphs and generalized connectivity

An edge‐colored tree T is a rainbow tree if no two edges of T are assigned the same color. Let G be a nontrivial connected graph of order n and let k be an integer with 2 ≤ k ≤ n . A k ‐rainbow coloring of G is an edge coloring of G having the property that for every set S of k vertices of G , there exists a rainbow tree T in G such that S ⊆ V ( T ). The minimum number of colors needed in a k ‐rainbow coloring of G is the k ‐rainbow index of G . For every two integers k and n ≥ 3 with 3 ≤ k ≤ n , the k ‐rainbow index of a unicyclic graph of order n is determined. For a set S of vertices in a connected graph G of order n , a collection { T 1 , T 2 ,…, T ℓ } of trees in G is said to be internally disjoint connecting S if these trees are pairwise edge‐disjoint and V ( T i ) ∩ V ( T j ) = S for every pair i , j of distinct integers with 1 ≤ i , j ≤ ℓ. For an integer k with 2 ≤ k ≤ n , the k ‐connectivity κ k ( G ) of G is the greatest positive integer ℓ for which G contains at least ℓ internally disjoint trees connecting S for every set S of k vertices of G . It is shown that κ k ( K n )= n −⌈ k /2⌉ for every pair k , n of integers with 2 ≤ k ≤ n . For a nontrivial connected graph G of order n and for integers k and ℓ with 2 ≤ k ≤ n and 1 ≤ ℓ ≤ κ k ( G ), the ( k ,ℓ)‐rainbow index rx k ,ℓ ( G ) of G is the minimum number of colors needed in an edge coloring of G such that G contains at least ℓ internally disjoint rainbow trees connecting S for every set S of k vertices of G . The numbers rx k ,ℓ ( K n ) are determined for all possible values k and ℓ when n ≤ 6. It is also shown that for ℓ ϵ {1, 2}, rx 3,ℓ ( K n ) = 3 for all n ≥ 6. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010