Rainbow connection number and the number of blocks

Xueliang Li, Sujuan Liu

Published 2012-11-01, updated 2012-11-05Version 2

An edge-colored graph $G$ is rainbow connected if every pair of vertices of $G$ are connected by a path whose edges have distinct colors. The rainbow connection number $rc(G)$ of $G$ is defined to be the minimum integer $t$ such that there exists an edge-coloring of $G$ with $t$ colors that makes $G$ rainbow connected. For a graph $G$ without any cut vertex, i.e., a 2-connected graph, of order $n$, it was proved that $rc(G)\leq \lceil\frac n 2 \rceil$ and the bound is tight. In this paper, we prove that for a connected graph $G$ of order $n$ with cut vertices, $rc(G) \leq\frac{n+r-1} 2$, where $r$ is the number of blocks of $G$ with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound for a bridgeless graph, i.e., a 2-edge-connected graph.