On the Rainbow and Strong Rainbow Connection Numbers of the m-Splitting of the Complete Graph K_n

摘要

An edge-coloring of a graph is called rainbow if any two vertices are connected by a path consisting of edges of different colors. The least number of colors in such a coloring is called the rainbow connection number of G, denoted by rc(G). An edge-coloring of a graph is called strong rainbow if any two vertices are connected by a geodesic consisting of edges of different colors. The least number of colors in such a coloring is called the strong rainbow connection number of G, denoted by src(G). In this paper we study the rc and src of the m-splitting of a graph. In particular we study Spl_m(K_n). We present the exact values of its rc and src in several cases, and we prove several bounds in the other cases.