paper

On the number of forests and connected spanning subgraphs

arXiv:2005.12752

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 G_{d}} F (G)^{1/ v (G)}$ , where $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$ .