Upper bound for the number of spanning forests of regular graphs

DOI10.1016/J.EJC.2022.103677arXiv2105.06801MaRDI QIDQ6367649FDOQ6367649

Authors: Ferenc Bencs, Péter Csikvári 

Publication date: 14 May 2021

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.

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)

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)