2013/06/29 by Lily Chen, Chen, Lily, Xueliang Li +5
Mathematics · #05C05 #05C15 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1307.0079
13 pages
arxiv created 2013/07/03 · arxiv updated 2013/07/04
Let G be a nontrivial connected graph with an edge-coloring c: E(G)→ \1,2,...,q\, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex subset S⊆ V(G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V(G) is called k-rainbow index, denoted by rxk(G). In this paper, we first determine the graphs whose 3-rainbow index equals 2, m, m-1, m-2, respectively. We also obtain the exact values of rx3(G) for regular complete bipartite and multipartite graphs and wheel graphs. Finally, we give a sharp upper bound for rx3(G) of 2-connected graphs and 2-edge connected graphs, and graphs whose rx3(G) attains the upper bound are characterized.