{
  "id": "2005.12752",
  "version": "v1",
  "published": "2020-05-26T14:19:31.000Z",
  "updated": "2020-05-26T14:19:31.000Z",
  "title": "On the number of forests and connected spanning subgraphs",
  "authors": [
    "Márton Borbényi",
    "Péter Csikvári",
    "Haoran Luo"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $F(G)$ be the number of forests of a graph $G$. Similarly let $C(G)$ be the number of connected spanning subgraphs of a connected graph $G$. We bound $F(G)$ and $C(G)$ for regular graphs and for graphs with fixed average degree. Among many other things we study $f_d=\\sup_{G\\in \\mathcal{G}_d}F(G)^{1/v(G)}$, where $\\mathcal{G}_d$ is the family of $d$--regular graphs, and $v(G)$ denotes the number of vertices of a graph $G$. We show that $f_3=2^{3/2}$, and if $(G_n)_n$ is a sequence of $3$--regular graphs with length of the shortest cycle tending to infinity, then $\\lim_{n\\to \\infty}F(G_n)^{1/v(G_n)}=2^{3/2}$. We also improve on the previous best bounds on $f_d$ for $4\\leq d\\leq 9$. We give various applications of our inequalities to grids.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-05-26T14:19:31.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "connected spanning subgraphs",
      "regular graphs",
      "fixed average degree",
      "best bounds",
      "shortest cycle"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}