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

A path in an edge-colored graph GG is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph GG, denoted by rc(G)rc(G), is the minimum number of colors that are needed to color the edges of GG such that there is a rainbow path connecting every two vertices of GG. Similarly, a tree in GG is a rainbow tree if no two edges of it receive the same color. The minimum number of colors that are needed in an edge-coloring of GG such that there is a rainbow tree containing all the vertices of SS (other vertices may also be included in the tree) for each kk-subset SS of V(G)V(G) is called the kk-rainbow index of GG, denoted by rxk(G)rxk(G), where kk is an integer such that 2≤k≤n2≤k≤n. Chakraborty et al. got the following result: For every ϵ>0ϵ>0, a connected graph with minimum degree at least ϵnϵn has bounded rainbow connection number, where the bound depends only on ϵϵ. Krivelevich and Yuster proved that if GG has nn vertices and the minimum degree δ(G)δ(G) then rc(G)<20n/δ(G)rc(G)<20n/δ(G). This bound was later improved to 3n/(δ(G)+1)+33n/(δ(G)+1)+3 by Chandran et al. Since rc(G)=rx2(G)rc(G)=rx2(G), a natural problem arises: for a general kk determining the true behavior of rxk(G)rxk(G) as a function of the minimum degree δ(G)δ(G). In this paper, we give upper bounds of rxk(G)rxk(G) in terms of the minimum degree δ(G)δ(G) in different ways, namely, via Szemerédi’s Regularity Lemma, connected 2-step dominating sets, connected (k−1)(k−1)-dominating sets and kk-dominating sets of GG.