Rainbow Connection Number, Bridges and Radius.

Let G be a connected graph. The notion of rainbow connection number rc( G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85-98, ). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], ) proved that for every bridgeless graph G with radius r, $${rc(G)\leq r(r+2)}$$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D = { u}, then G has r−1 connected dominating sets $${ D^{r-1}, D^{r-2},\ldots, D^{1}}$$ such that $${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$$ and $${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$$, where b is the number of bridges in E[ D, N( D)] for $${1\leq i \leq r}$$. From the result, we can get that if $${b_i\leq 2i+1}$$ for all $${1\leq i\leq r}$$, then $${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$$; if b > 2 i + 1 for all $${1\leq i\leq r}$$ , then $${rc(G)= \sum_{i=1}^{r}b_i}$$, the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc( G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc( G) is only dependent on the number of bridges in G. [ABSTRACT FROM AUTHOR]