Rainbow Connection Number, Bridges and Radius
Abstrak
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 Dr = {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 bi is the number of bridges in E[Di, N(Di)] 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 bi > 2i + 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.
Topik & Kata Kunci
Penulis (2)
Jiuying Dong
Xueliang Li
Akses Cepat
- Tahun Terbit
- 2011
- Bahasa
- en
- Total Sitasi
- 11×
- Sumber Database
- Semantic Scholar
- DOI
- 10.1007/s00373-012-1218-3
- Akses
- Open Access ✓