Rainbow connection number, bridges and radius

Abstract

Let $G$ be a connected graph. The notion \emph{the rainbow connection number $rc(G)$} of a graph $G$ was introduced recently by Chartrand et al. Basavaraju et al. showed that for every bridgeless graph $G$ with radius $r$, $rc(G)\le r(r+2)$, and the bound is tight. In this paper, we prove that if $G$ is a connected graph, and $D^k$ is a connected $k$-step dominating set of $G$, then $G$ has a connected $(k-1)$-step dominating set $D^{k-1}\supset D^k$ such that $rc(G[D^{k-1}])\le rc(G[D^k])+\max \{2k+1,b_k\}$, where $b_k$ is the number of bridges in $E(D^k,N(D^k))$. Furthermore, for a connected graph $G$ with radius $r$, let $u$ be the center of $G$, and $D^r=\{u\}$. Then $G$ has $r-1$ connected dominating sets $D^{r-1},D^{r-2},...,D^1$ satisfying $D^r\subset D^{r-1}\subset D^{r-2}...\subset D^1\subset D^0=V(G)$, and $rc(G)\le {\sum }_{i=1}^r\max \{2i+1,b_i\}$, where $b_i$ is the number of bridges in $E(D^i,N(D^i)),1\le i\le r$. From the result, we can get that if for all $1\le i\le r,b_i\le 2i+1$, then $rc(G)\le {\sum }_{i=1}^r(2i+1)=r(r+2)$; if for all $1\le i\le r,b_i>2i+1$, then $rc(G)={\sum }_{i=1}^r{b}_i$, the number of bridges of $G$. This generalizes the result of Basavaraju et al.

8 pages

Cited by in corpus (1)

• Rainbow Connection Number of Graph Power and Graph Products