{
  "id": "1205.5163",
  "version": "v1",
  "published": "2012-05-23T12:18:53.000Z",
  "updated": "2012-05-23T12:18:53.000Z",
  "title": "Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least~4",
  "authors": [
    "Dmitri Karpov"
  ],
  "comment": "26 pages. Russian version: POMI Preprint 16/2011, http://www.pdmi.ras.ru/preprint/2011/11-16.html",
  "journal": "Journal of Mathematical Sciences, Volume 196, Issue 6 (2014), pp 768-783",
  "doi": "10.1007/s10958-014-1692-7",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that every connected graph with $s$ vertices of degree~1 and 3 and $t$ vertices of degree at least~4 has a spanning tree with at least ${1\\over 3}t +{1\\over 4}s+{3\\over 2}$ leaves. We present infinite series of graphs showing that our bound is tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-05-23T12:18:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C07"
    ],
    "keywords": [
      "spanning tree",
      "lower bounds",
      "infinite series",
      "connected graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1205.5163K"
    }
  }
}