{
  "id": "0906.3946",
  "version": "v1",
  "published": "2009-06-22T08:20:23.000Z",
  "updated": "2009-06-22T08:20:23.000Z",
  "title": "The rainbow $k$-connectivity of two classes of graphs",
  "authors": [
    "Xueliang Li",
    "Yuefang Sun"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A path in an edge-colored graph $G$, where adjacent edges may be colored the same, is called a rainbow path if no two edges of $G$ are colored the same. For a $\\kappa$-connected graph $G$ and an integer $k$ with $1\\leq k\\leq \\kappa$, the rainbow $k$-connectivity $rc_k(G)$ of $G$ is defined as the minimum integer $j$ for which there exists a $j$-edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by $k$ internally disjoint rainbow paths. Let $G$ be a complete $(\\ell+1)$-partite graph with $\\ell$ parts of size $r$ and one part of size $p$ where $0\\leq p <r$ (in the case $p=0$, $G$ is a complete $\\ell$-partite graph with each part of size $r$). This paper is to investigate the rainbow $k$-connectivity of $G$. We show that for every pair of integers $k\\geq 2$ and $r\\geq 1$, there is an integer $f(k,r)$ such that if $\\ell\\geq f(k,r)$, then $rc_k(G)=2$. As a consequence, we improve the upper bound of $f(k)$ from $(k+1)^2$ to $ck^{{3/2}}+C$, where $0<c<1$, $C=o(k^{{3/2}})$, and $f(k)$ is the integer such that if $n \\geq f(k)$ then $rc_k(K_n)=2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-06-22T08:20:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40"
    ],
    "keywords": [
      "connectivity",
      "partite graph",
      "internally disjoint rainbow paths",
      "adjacent edges",
      "minimum integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0906.3946L"
    }
  }
}