{
  "id": "1204.0392",
  "version": "v2",
  "published": "2012-04-02T12:51:34.000Z",
  "updated": "2012-04-11T05:34:21.000Z",
  "title": "A sharp upper bound for the rainbow 2-connection number of 2-connected graphs",
  "authors": [
    "Xueliang Li",
    "Sujuan Liu"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A path in an edge-colored graph is called {\\em rainbow} if no two edges of it are colored the same. For an $\\ell$-connected graph $G$ and an integer $k$ with $1\\leq k\\leq \\ell$, the {\\em rainbow $k$-connection number} $rc_k(G)$ of $G$ is defined to be the minimum number of colors required to color the edges of $G$ such that every two distinct vertices of $G$ are connected by at least $k$ internally disjoint rainbow paths. Fujita et. al. proposed a problem that what is the minimum constant $\\alpha>0$ such that for all 2-connected graphs $G$ on $n$ vertices, we have $rc_2(G)\\leq \\alpha n$. In this paper, we prove that $\\alpha=1$ and $rc_2(G)=n$ if and only if $G$ is a cycle of order $n$, settling down this problem.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-04-11T05:34:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C40",
      "05C15"
    ],
    "keywords": [
      "sharp upper bound",
      "internally disjoint rainbow paths",
      "minimum constant",
      "minimum number",
      "distinct vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1204.0392L"
    }
  }
}