{
  "id": "1101.3119",
  "version": "v1",
  "published": "2011-01-17T03:47:20.000Z",
  "updated": "2011-01-17T03:47:20.000Z",
  "title": "Upper bounds involving parameter $σ_2$ for the rainbow connection",
  "authors": [
    "Jiuying Dong",
    "Xueliang Li"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a graph $G$, we define $\\sigma_2(G)=min \\{d(u)+d(v)| u,v\\in V(G), uv\\not\\in E(G)\\}$, or simply denoted by $\\sigma_2$. A edge-colored graph is rainbow edge-connected if any two vertices are connected by a path whose edges have distinct colors, which was introduced by Chartrand et al. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow edge-connected. We prove that if $G$ is a connected graph of order $n$, then $rc(G)\\leq 6\\frac{n-2}{\\sigma_2+2}+7$. Moreover, the bound is seen to be tight up to additive factors by a construction mentioned by Caro et al. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was recently introduced by Krivelevich and Yuster. The rainbow vertex-connection of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. We prove that if $G$ is a connected graph of order $n$, then $rvc(G)\\leq 8\\frac{n-2}{\\sigma_2+2}+10 $ for $2\\leq \\sigma_2\\leq 6, \\sigma_2\\geq 28 $, while for $ 7 \\leq \\sigma_2\\leq 8, 16\\leq \\sigma_2\\leq 27$, $ rvc(G)\\leq \\frac{10n-16}{\\sigma_2+2}+10$, and for $9 \\leq \\sigma_2\\leq 15, rvc(G)\\leq \\frac{10n-16}{\\sigma_2+2}+A(\\sigma_2)$ where $ A(\\sigma_2)= 63,41,27,20,16,13,11,$ respectively.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-01-17T03:47:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40"
    ],
    "keywords": [
      "rainbow connection",
      "upper bounds",
      "connected graph",
      "smallest number",
      "distinct colors"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1101.3119D"
    }
  }
}