Upper bound for the number of spanning forests of regular graphs

Abstract

We show that if $G$ is a $d$--regular graph on $n$ vertices, then the number of spanning forests $F(G)$ satisfies $F(G)\le d^n$. The previous best bound due to Kahale and Schulman gave $(d+1/2+O(1/d){)}^n$. We also have the more precise conjecture that $$F(G{)}^{1/n}\le \frac{(d-1{)}^{d-1}}{(d^2-2d-1{)}^{d/2-1}}.$$ If this conjecture is true, then the expression on the right hand side is the best possible.

arXiv commentarXiv admin note: text overlap with arXiv:2105.06798