The 3-rainbow index and connected dominating sets

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$$ G is called a 3-rainbow coloring if for any three vertices in $$G$$ G , there exists a rainbow tree connecting them. The 3-rainbow index $$rx_3(G)$$ r x 3 ( G ) of $$G$$ G is defined as the minimum number of colors that are needed in a 3-rainbow coloring of $$G$$ 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 3-way dominating sets and 3-dominating sets. We show that for every connected graph $$G$$ G on $$n$$ n vertices with minimum degree at least $$\delta \, (3\le \delta \le 5)$$ δ ( 3 ≤ δ ≤ 5 ) , $$rx_{3}(G)\le \frac{3n}{\delta +1}+4$$ r x 3 ( G ) ≤ 3 n δ + 1 + 4 , and the bound is tight up to an additive constant; whereas for every connected graph $$G$$ G on $$n$$ n vertices with minimum degree at least $$\delta \, (\delta \ge 3)$$ δ ( δ ≥ 3 ) , we get that $$rx_{3}(G)\le \frac{\ln (\delta +1)}{\delta +1}(1+o_{\delta }(1))n+5$$ r x 3 ( G ) ≤ ln ( δ + 1 ) δ + 1 ( 1 + o δ ( 1 ) ) n + 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.