The strong 3-rainbow index of graphs containing some cycles

Abstract

A tree of minimum size in an edge-colored connected graph G is a rainbow Steiner tree if no two edges of G are colored the same. For an integer k, the strong k-rainbow index $srx_k(G)$ of G is the smallest number of colors required in an edge-coloring of G so that there exists a rainbow Steiner tree connecting every k-subset S of V(G). We focus on k=3. It is obvious that $srx_3(G)\leq\lVert G\rVert$ where $\lVert G\rVert$ denotes the size of G. It has been proven that $srx_3(T_n)=\lVert T_n\rVert$. In this paper, we study how the $srx_3(T_n)$ changes when we add at least one edge to $T_n$. We provide a sharp upper bound and exact values of $srx_3(G)$ where G is a graph containing at most two cycles. We obtain that $srx_3(G)=\lVert G\rVert$ where G is a unicyclic graph of girth 7 or at least 9. Otherwise, $srx_3(G)<\lVert G\rVert$.