{
  "id": "1705.10254",
  "version": "v1",
  "published": "2017-05-29T15:26:36.000Z",
  "updated": "2017-05-29T15:26:36.000Z",
  "title": "An Erdős-Gallai-type theorem for keyrings",
  "authors": [
    "Alexander Sidorenko"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A keyring is a graph obtained by appending $r \\geq 1$ leaves to one of the vertices of a circle. We prove that for every $r \\leq (k-1)/2$, any graph with average degree more than $k-1$ contains a keyring with $r$ leaves and at least $k$ edges. We also prove the validity of the Erd\\H{o}s-S\\'{o}s conjecture for some classes of trees.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-05-29T15:26:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C05"
    ],
    "keywords": [
      "erdős-gallai-type theorem",
      "average degree",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}