Rainbow Trees in Graphs and Generalized Connectivity

摘要

An edge-colored tree 7 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 is contained in 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 rnorder n, a collection {T_1, T_2.....T_l} of trees in G is saidrnto be internally disjoint connecting S if these trees are pairwise edge-disjoint and V(T_i) n V(T_j) = S for every pair i,j of distinct integers with 1 ≤ i,j ≤ l. For an integer k with 2 ≤ k ≤ n, the k-connectivity K_k(G) of G is the greatest positive integer l for which G contains at least t internally disjoint trees connecting S for every set S of k vertices of G.It is shown that IC_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 l with 2 ≤ k ≤ n and 1 ≤ l ≤ K_k(G), the (k,l)-rainbow index rx_(k,l)(G) of G is the minimum number of colors needed in an edge coloring of G such that G contains at least l internally disjoint rainbow trees connecting S for every set S of k vertices of G. The numbers rx_(k,l)(K_n) are determined for all possible values k and l when n ≤ 6. It is also shown that for l ∈ {1,2}, rx_(3,l)(K_n) = 3 for all n ≥ 6.