{
  "id": "1105.0790",
  "version": "v1",
  "published": "2011-05-04T11:07:36.000Z",
  "updated": "2011-05-04T11:07:36.000Z",
  "title": "Rainbow connection number, bridges and radius",
  "authors": [
    "Jiuying Dong",
    "Xueliang Li"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "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)\\leq 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}])\\leq 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)\\leq \\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\\leq i \\leq r$. From the result, we can get that if for all $1\\leq i\\leq r, b_i\\leq 2i+1$, then $rc(G)\\leq \\sum_{i=1}^{r}(2i+1)= r(r+2)$; if for all $1\\leq i\\leq 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-05-04T11:07:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40"
    ],
    "keywords": [
      "rainbow connection number",
      "connected graph",
      "step dominating set",
      "basavaraju",
      "generalizes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.0790D"
    }
  }
}