Some upper bounds for 3-rainbow index of graphs

Abstract

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 coloring}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 {\em $k$-rainbow index of $G$}, denoted by $r{x}_k(G)$. In this paper, we consider 3-rainbow index $r{x}_3(G)$ of $G$. We first show that for connected graph $G$ with minimum degree $\delta (G)\ge 3$, the tight upper bound of $r{x}_3(G)$ is $r{x}_3(G[D])+4$, where $D$ is the connected 2-dominating set of $G$. And then we determine a tight upper bound for $K_{s,t}(3\le s\le t)$ and a better bound for $(P_5,C_5)$-free graphs. Finally, we obtain a sharp bound for 3-rainbow index of general graphs.

7 pages 1 figures

References in corpus (1)

• Rainbow Connection Number and Connected Dominating Sets

Cited by in corpus (4)

• The 3-rainbow index of graph operations
• The 3-rainbow index and connected dominating sets
• The $k$-proper index of complete bipartite and complete multipartite graphs
• Note on the upper bound of the rainbow index of a graph