Rainbow connection number and the number of blocks

Abstract

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)\le \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)\le \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.

7 pages