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, 2008). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], 2010) 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 ^r  = {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} cdotssubset D^{1} subset D^{0}=V(G)}$ and ${rc(G)leq sum_{i=1}^{r} max {2i+1,b_i}}$ , where b _i is the number of bridges in E[D ⁱ , N(D ⁱ )] for ${1leq i leq r}$ . From the result, we can get that if ${b_ileq 2i+1}$ for all ${1leq ileq r}$ , then ${rc(G)leq sum_{i=1}^{r}(2i+1)= r(r+2)}$ ; if b _i  > 2i + 1 for all ${1leq ileq 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.