Upper bounds for the number of spanning forests of a graph
Source: arxiv.org/abs/2611.18076
Let $G$ be a simple graph on $n$ vertices, and let $F(G)$ denote the number of spanning forests of $G$. Bencs and Csikvári proved that every $r$-regular graph $G$ with $r\ge 2$ satisfies $F(G)\le r^n$. Motivated by this result, they conjectured that if $G$ has minimum degree at least $3$, then $F(G)\leq \prod_{i=1}^n d_i$, where $(d_1, d_2, \dots, d_n)$ is the degree sequence of $G$. In this paper, we prove that graphs with minimum degree at least $n/3$ $(n\geq7)$ satisfy $F(G)\leq \prod_{i=1}^n d_i$. We also construct a counterexample to the conjecture. We therefore further study the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.18076
curl -X POST /api/v1/records/arxiv/2611.18076/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18076/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'