{
  "id": "1004.2312",
  "version": "v1",
  "published": "2010-04-14T04:14:21.000Z",
  "updated": "2010-04-14T04:14:21.000Z",
  "title": "Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs",
  "authors": [
    "Xueliang Li",
    "Yuefang Sun"
  ],
  "comment": "6 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 the path 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 any two distinct vertices of $G$ are connected by $k$ internally disjoint rainbow paths. Denote by $K_{r,r}$ an $r$-regular complete bipartite graph. Chartrand et al. in \"G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54(2009), 75-81\" left an open question of determining an integer $g(k)$ for which the rainbow $k$-connectivity of $K_{r,r}$ is 3 for every integer $r\\geq g(k)$. This short note is to solve this question by showing that $rc_k(K_{r,r})=3$ for every integer $r\\geq 2k\\lceil\\frac{k}{2}\\rceil$, where $k\\geq 2$ is a positive integer.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-04-14T04:14:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40"
    ],
    "keywords": [
      "regular complete bipartite graph",
      "connectivity",
      "internally disjoint rainbow paths",
      "adjacent edges",
      "distinct vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1004.2312L"
    }
  }
}