Note on the upper bound of the rainbow index of a graph ?
A path in an edge-colored graph G G is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph G G , denoted by rc(G) r c ( G ) , is the minimum number of colors that are needed to color the edges of G G such that there is a rainbow path connecting every two vertices of G G . Similarly, a tree in G G is a rainbowtree if no two edges of it receive the same color. The minimum number of colors that are needed in an edge-coloring of G G such that there is a rainbow tree containing all the vertices of S S (other vertices may also be included in the tree) for each k k -subset S S of V(G) V ( G ) is called the k k -rainbow index of G G , denoted by rxk(G) r x k ( G ) , where k k is an integer such that 2?k?n 2 ? k ? n . Chakraborty etal. 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 G G has n n vertices and the minimum degree ?(G) ? ( G ) then rc(G)<20n/?(G) r c ( G ) < 20 n / ? ( G ) . This bound was later improved to 3n/(?(G)+1)+3 3 n / ( ? ( G ) + 1 ) + 3 by Chandran etal. Since rc(G)=rx2(G) r c ( G ) = r x 2 ( G ) , a natural problem arises: for a general k k determining the true behavior of rxk(G) r x k ( G ) as a function of the minimum degree ?(G) ? ( G ) . In this paper, we give upper bounds of rxk(G) r x k ( G ) in terms of the minimum degree ?(G) ? ( G ) in different ways, namely, via Szemerdis Regularity Lemma, connected 2-step dominating sets, connected (k?1) ( k ? 1 ) -dominating sets and k k -dominating sets of G G .
rainbow path rainbow tree dominating set k k -rainbow index k k k k k