2023-05-01
Upper bound for the number of spanning forests of regular graphs
Publication
Publication
European Journal of Combinatorics , Volume 110 p. 103677:1- 103677:12
We show that if G is a d–regular graph on n vertices, then the number of spanning forests F (G) satisfies F (G) ≤ dn. 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 ≤ (d − 1)d−1 (d2 − 2d − 1)d/2−1 . If this conjecture is true, then the expression on the right hand side is the best possible.
| Additional Metadata | |
|---|---|
| doi.org/10.1016/j.ejc.2022.103677 | |
| European Journal of Combinatorics | |
|
Bencs, F., & Csikvári, P. (2023). Upper bound for the number of spanning forests of regular graphs. European Journal of Combinatorics, 110, 103677:1–103677:12. doi:10.1016/j.ejc.2022.103677 |
|
