The 3-rainbow index and connected dominating sets

Abstract

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 $r{x}_3(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 $\delta$ ($3\le \delta \le 5$), $r{x}_3(G)\le \frac{3n}{\delta +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 $\delta$ ($\delta \ge 3$), we get that $r{x}_3(G)\le n\frac{ln(\delta +1)}{\delta +1}(1+o_{\delta }(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.

23 pages

Cited by in corpus (1)

• Note on the upper bound of the rainbow index of a graph