Upper bound for the number of spanning forests of regular graphs
| Authors |
|
|---|---|
| Publication date | 05-2023 |
| Journal | European Journal of Combinatorics |
| Article number | 103677 |
| Volume | Issue number | 110 |
| Number of pages | 12 |
| Organisations |
|
| 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)≤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≤[Formula presented].If this conjecture is true, then the expression on the right hand side is the best possible. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1016/j.ejc.2022.103677 |
| Downloads |
Upper bound for the number of spanning forests of regular graphs
(Final published version)
|
| Permalink to this page | |