On the Rainbow Connection Number of Graphs

Abstract

Let $G=(V,E)$, with $|V|=n$, be a simple connected graph. An edge-colored graph $G$ is rainbow edge-connected if any two vertices are connected by a path whose edges are colored by distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow edge-connected. In this paper, we obtain tight bounds for $rc(G)$. We use our results to generalize previous results for graphs with $\delta (G)\ge 3$.