Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
2  
McKay's paper is "B. McKay, Spanning trees in regular graphs, European Journal of Combinatorics 4 (1983) 149–160." –  j.c. Aug 30 '11 at 19:41
2  
Available at cs.anu.edu.au/~bdm/papers/SpanningTrees1983.pdf . Incidentally Fan Chung proved the conjecture which is stated just before the Acknowledgements, but there is an error in the precise upper bound she proved. I don't know if it is resolved yet. Her paper is here: combinatorics.org/Volume_6/Abstracts/v6i1r12.html . –  Brendan McKay Aug 30 '11 at 22:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.