{
  "id": "1406.0606",
  "version": "v1",
  "published": "2014-06-03T07:38:46.000Z",
  "updated": "2014-06-03T07:38:46.000Z",
  "title": "Induced Cycles in Graphs",
  "authors": [
    "Michael A. Henning",
    "Felix Joos",
    "Christian Löwenstein",
    "Thomas Sasse"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The maximum cardinality of an induced $2$-regular subgraph of a graph $G$ is denoted by $c_{\\rm ind}(G)$. We prove that if $G$ is an $r$-regular graph of order $n$, then $c_{\\rm ind}(G) \\geq \\frac{n}{2(r-1)} + \\frac{1}{(r-1)(r-2)}$ and we prove that if $G$ is a cubic claw-free graph on order $n$, then $c_{\\rm ind}(G) > 13n/20$ and this bound is asymptotically best possible.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-06-03T07:38:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "induced cycles",
      "cubic claw-free graph",
      "regular graph",
      "regular subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1406.0606H"
    }
  }
}