Rainbow Connection Number and Independence Number of a Graph

Abstract

A path in an edge-colored graph is called rainbow if any two edges of the path have distinct colors. An edge-colored graph is called rainbow connected if there exists a rainbow path between every two vertices of the graph. For a connected graph G, the minimum number of colors that are needed to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if G is a connected graph without pendant vertices, then $\mathrm{rc}(G)\le 2\alpha (G)-1$. An example is given showing that the upper bound $2\alpha (G)-1$ is equal to the diameter of G, and so the upper bound is sharp since the diameter of G is a lower bound of $\mathrm{rc}(G)$.