PreprintCC BY 4.0arXiv
A sharp upper bound on the number of spanning forests of regular graphs
Abstract
Let G be a simple graph on n vertices, and let F(G) denote the number of its spanning forests. Bencs and Csikvári [Upper bound for the number of spanning forests of regular graphs, European J. Combin. 110 (2023) 103677] proved that every r-regular graph G with r≥ 2 satisfies F(G) ≤ rn. They further conjectured that for r ≥ 3, F(G)1/n ≤ ((r − 1)r−1)/((r2 − 2r − 1)r/2−1). In this paper, we resolve this conjecture in the affirmative.
Related
- Sharp Bounds for Common Spanning Forests under Color Refinement
- Rooted spanning forests in wheel graphs: Fibonacci-Lucas formulas and extremal root configurations
- Maximum number of spanning trees in bipartite graphs with a given diameter
- A Turán-type extremal problem for the number of spanning trees in C4-free graphs
- Wild number for spanning trees in complete and complete bipartite graphs
BibTeX
@misc{wu2026sharp,
title = {{A sharp upper bound on the number of spanning forests of regular graphs}},
author = {T. Wu and S. Lu and X. Dong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05722},
eprint = {2610.05722},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05722},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A sharp upper bound on the number of spanning forests of regular graphs
AU - T. Wu
AU - S. Lu
AU - X. Dong
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05722
UR - https://arxiv.org/abs/2610.05722
AB - Let G be a simple graph on n vertices, and let F(G) denote the number of its spanning forests. Bencs and Csikvári [Upper bound for the number of spanning forests of regular graphs, European J. Combin. 110 (2023) 103677] proved that every r-regular graph G with r≥ 2 satisfies F(G) ≤ r^n. They further conjectured that for r ≥ 3, F(G)^1/n ≤ ((r − 1)^r−1)/((r^2 − 2r − 1)^r/2−1). In this paper, we resolve this conjecture in the affirmative.
ER -