2013/10/09 by Tingting Liu, Liu, Tingting, Yumei Hu +1
Mathematics · #05C05 #05C15 #05C69 #05C85 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C69 #msc:05C85
paper · pdf · doi:10.48550/arxiv.1310.2355
7 pages 1 figures
arxiv created 2013/10/09 · arxiv updated 2013/10/10
A tree T, in an edge-colored graph G, is called \em a rainbow tree if no two edges of T are assigned the same color. A \em k-rainbow coloringof 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 \em k-rainbow index of G, denoted by rxk(G). In this paper, we consider 3-rainbow index rx3(G) of G. We first show that for connected graph G with minimum degree δ(G)≥ 3, the tight upper bound of rx3(G) is rx3(G[D])+4, where D is the connected 2-dominating set of G. And then we determine a tight upper bound for Ks,t(3≤ s≤ t) and a better bound for (P5,C5)-free graphs. Finally, we obtain a sharp bound for 3-rainbow index of general graphs.