Some upper bounds for $3$-rainbow index of graphs

Abstract

A tree $T$, in an edge-colored graph $G$, is called a $rainbowtree$ if no two edges of $T$ are assigned the same color. A $k$-$rainbowcoloring$ of $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\subseteq V(T)$. The minimum number of colors needed in a $k$-rainbow coloring of $G$ is the $k$-$rainbowindex$ of $G$, denoted by ${\text{rx}}_k(G)$. In this paper, we investigate the $3$-rainbow index ${\text{rx}}_3(G)$ of a connected graph $G$. For a connected graph $G$, it is shown that a sharp upper bound of ${\text{rx}}_3(G)$ is ${\text{rx}}_3(G[D])+4$, where $D$ is a connected 3-way dominating set and a connected 2-dominating set of $G$. Moreover, we determine a sharp upper bound for $K_{s,t}$ ($3\le s\le t$) and a better bound for $(P_5,C_5)$-free graphs, respectively. Finally, a sharp bound for the $3$-rainbow index of general graphs is obtained.