{
  "id": "1203.3030",
  "version": "v1",
  "published": "2012-03-14T09:35:41.000Z",
  "updated": "2012-03-14T09:35:41.000Z",
  "title": "Note on minimally $k$-rainbow connected graphs",
  "authors": [
    "Hengzhe Li",
    "Xueliang Li",
    "Yuefang Sun",
    "Yan Zhao"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An edge-colored graph $G$, where adjacent edges may have the same color, is {\\it rainbow connected} if every two vertices of $G$ are connected by a path whose edge has distinct colors. A graph $G$ is {\\it $k$-rainbow connected} if one can use $k$ colors to make $G$ rainbow connected. For integers $n$ and $d$ let $t(n,d)$ denote the minimum size (number of edges) in $k$-rainbow connected graphs of order $n$. Schiermeyer got some exact values and upper bounds for $t(n,d)$. However, he did not get a lower bound of $t(n,d)$ for $3\\leq d<\\lceil\\frac{n}{2}\\rceil $. In this paper, we improve his lower bound of $t(n,2)$, and get a lower bound of $t(n,d)$ for $3\\leq d<\\lceil\\frac{n}{2}\\rceil$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-03-14T09:35:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C40"
    ],
    "keywords": [
      "rainbow connected graphs",
      "lower bound",
      "adjacent edges",
      "upper bounds",
      "distinct colors"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.3030L"
    }
  }
}