2014/04/09 by Qingqiong Cai, Xueliang Li, Cai, Qingqiong +3
Mathematics · #05C15 #05C38 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C38 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1404.2377
23 pages
arxiv created 2014/04/14 · arxiv updated 2014/04/15
A tree in an edge-colored graph is said to be rainbow if no two edges on the tree share the same color. An edge-coloring of G is called 3-rainbow if for any three vertices in G, there exists a rainbow tree connecting them. The 3-rainbow index rx3(G) of G is defined as the minimum number of colors that are needed in a 3-rainbow coloring of G. This concept, introduced by Chartrand et al., can be viewed as a generalization of the rainbow connection. In this paper, we study the 3-rainbow index by using connected three-way dominating sets and 3-dominating sets. We shown that for every connected graph G on n vertices with minimum degree at least δ (3≤δ≤5), rx3(G)≤ (3n)/(δ+1)+4, and the bound is tight up to an additive constant; whereas for every connected graph G on n vertices with minimum degree at least δ (δ≥3), we get that rx3(G)≤ n(ln(δ+1))/(δ+1)(1+oδ(1))+5. In addition, we obtain some tight upper bounds of the 3-rainbow index for some special graph classes, including threshold graphs, chain graphs and interval graphs.