{
  "id": "1012.1942",
  "version": "v2",
  "published": "2010-12-09T08:56:17.000Z",
  "updated": "2012-03-05T05:54:03.000Z",
  "title": "On Rainbow-$k$-Connectivity of Random Graphs",
  "authors": [
    "Jing He",
    "Hongyu Liang"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A path in an edge-colored graph is called a \\emph{rainbow path} if all edges on it have pairwise distinct colors. For $k\\geq 1$, the \\emph{rainbow-$k$-connectivity} of a graph $G$, denoted $rc_k(G)$, is the minimum number of colors required to color the edges of $G$ in such a way that every two distinct vertices are connected by at least $k$ internally disjoint rainbow paths. In this paper, we study rainbow-$k$-connectivity in the setting of random graphs. We show that for every fixed integer $d\\geq 2$ and every $k\\leq O(\\log n)$, $p=\\frac{(\\log n)^{1/d}}{n^{(d-1)/d}}$ is a sharp threshold function for the property $rc_k(G(n,p))\\leq d$. This substantially generalizes a result due to Caro et al., stating that $p=\\sqrt{\\frac{\\log n}{n}}$ is a sharp threshold function for the property $rc_1(G(n,p))\\leq 2$. As a by-product, we obtain a polynomial-time algorithm that makes $G(n,p)$ rainbow-$k$-connected using at most one more than the optimal number of colors with probability $1-o(1)$, for all $k\\leq O(\\log n)$ and $p=n^{-\\epsilon(1\\pm o(1))}$ for some constant $\\epsilon\\in[0,1)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-03-05T05:54:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graphs",
      "connectivity",
      "sharp threshold function",
      "internally disjoint rainbow paths",
      "distinct vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1012.1942H"
    }
  }
}