{
  "id": "2312.13674",
  "version": "v1",
  "published": "2023-12-21T08:54:45.000Z",
  "updated": "2023-12-21T08:54:45.000Z",
  "title": "Spanning trees for many different numbers of leaves",
  "authors": [
    "Kenta Noguchi",
    "Carol T. Zamfirescu"
  ],
  "comment": "7 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a connected graph and $L(G)$ the set of all integers $k$ such that $G$ contains a spanning tree with exactly $k$ leaves. We show that for a connected graph $G$, the set $L(G)$ is contiguous. It follows from work of Chen, Ren, and Shan that every connected and locally connected $n$-vertex graph -- this includes triangulations -- has a spanning tree with at least $n/2 + 1$ leaves, so by a classic theorem of Whitney and our result, in any plane $4$-connected $n$-vertex triangulation one can find for any integer $k$ which is at least~2 and at most $n/2 + 1$ a spanning tree with exactly $k$ leaves (and each of these trees can be constructed in polynomial time). We also prove that there exist infinitely many $n$ such that there is a plane $4$-connected $n$-vertex triangulation containing a spanning tree with $2n/3$ leaves, but no spanning tree with more than $2n/3$ leaves.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-21T08:54:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C10"
    ],
    "keywords": [
      "spanning tree",
      "vertex triangulation",
      "connected graph",
      "polynomial time",
      "vertex graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}