Sharp estimates for spanning trees
| Autor: | Klee, Steven, Narayanan, Bhargav, Sauermann, Lisa |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We prove the following sharp estimate for the number of spanning trees of a graph in terms of its vertex-degrees: a simple graph $G$ on $n$ vertices has at most $(1/n^{2}) \prod_{v \in V(G)} (d(v)+1)$ spanning trees. This result is tight (for complete graphs), and improves earlier estimates of Alon from 1990 and Kostochka from 1995 by a factor of about $1/n$ (for dense graphs). We additionally show that an analogous bound holds for the weighted spanning tree enumerator of a (nonnegatively) weighted graph as well. Comment: It has been pointed out to us when this paper was under review that the results are not new; in fact a stronger bound was proved by Grone and Merris [Discrete Math. 69 (1988), 97-99] |
| Databáze: | arXiv |
| Externí odkaz: |
|