Bounds on spanning tree for sparse graphs

Question

In mathoverflow posting 43081, the question was raised of bounding the number of spanning trees of a graph in terms of $m, n$, the number of edges and vertices. I am interested in the case when $m$ is small compared to $n$ (say $m = c n$ for $c \rightarrow 1$.). In this case, the best bound I have been able to find is the obvious bound $$ \kappa \leq \binom{m}{n-1} $$

There are a lot of papers describing tighter bounds when $m$ is large, such as the bound $\kappa < (2 m/n)^{n-1}$. But are there are any better bounds available in the regime when $m$ is small?

Thanks for any pointers!

Answer 1

Two bounds I found in my old files:

Grimmett, Disc Math 16 (1976) 323-324. Two bounds: $$ \frac{1}{n}\left( \frac{2m}{n-1} \right)^{n-1}.$$ $$ \left( \frac{2m-d}{n-1} \right)^{n-1},$$ where $d$ is the maximum degree. This second one is exact for $K_{1,n-1}$.

Grone and Merris, Disc Math 69 (1988) 97-99. $$ \left( \frac{n}{n-1} \right)^{n-1} \frac{\prod d_i}{\sum d_i},$$ where $d_i$ are the degrees.

In this 1981 paper of mine: http://cs.anu.edu.au/~bdm/papers/Subgraphs1981.pdf , I found the average number of spanning trees within a constant, for random graphs with bounded specified degrees. It is a fun formula as it has both the arithmetic and geometric means of the degrees mixed together (p221). This doesn't give the maximum number of spanning trees, but one can ask if the maximum can be exponentially more than the average, which is not the case for regular graphs.

Answer 2

Yes. See this paper:

www.intlpress.com/JOC/p/2010/JOC-1-2-a1-Thomassen.pdf

(Carsten Thomassen, spanning trees and orientations in graphs; google shows you the full text...), and references therein (esp. McKay's paper [9, op cit])

He treats cubic graphs, which is about as sparse as you can get, but I am sure some of the techniques extend to at least the $k$-regular case.