Upper bound for the number of spanning forests of regular graphs

DOI10.1016/J.EJC.2022.103677MaRDI QIDQ6367649arXivFDO

Authors Ferenc Bencs, Péter Csikvári

Publication date 14 May 2021

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Graph polynomials (05C31) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

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)leq{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 ${\displaystyle }$F(G)^{1/n}leq frac{(d-1)^{d-1}}{(d^2-2d-1)^{d/2-1}}.${\displaystyle }$ If this conjecture is true, then the expression on the right hand side is the best possible.

This page was built for publication: Upper bound for the number of spanning forests of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367649)