{
  "id": "1202.3082",
  "version": "v1",
  "published": "2012-02-14T16:38:24.000Z",
  "updated": "2012-02-14T16:38:24.000Z",
  "title": "Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4",
  "authors": [
    "D. V. Karpov"
  ],
  "comment": "33 pages, 15 figures",
  "journal": "Journal of Mathematical Sciences, Volume 196, Issue 6 (2014), pp 747-767",
  "doi": "10.1007/s10958-014-1691-8",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We prove, that every connected graph with $s$ vertices of degree 3 and $t$ vertices of degree at least~4 has a spanning tree with at least ${2\\over 5}t +{1\\over 5}s+\\alpha$ leaves, where $\\alpha \\ge {8\\over 5}$. Moreover, $\\alpha \\ge 2$ for all graphs besides three exclusions. All exclusion are regular graphs of degree~4, they are explicitly described in the paper. We present infinite series of graphs, containing only vertices of degrees~3 and~4, for which the maximal number of leaves in a spanning tree is equal for ${2\\over 5}t +{1\\over 5}s+2$. Therefore we prove that our bound is tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-02-14T16:38:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05"
    ],
    "keywords": [
      "spanning tree",
      "lower bounds",
      "maximal number",
      "regular graphs",
      "infinite series"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1202.3082K"
    }
  }
}