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

The Kirchhoff's theorem is a classical result for counting the number of spanning trees in a graph.

However, what are the best known upper bounds on the number of spanning trees in a graph in terms of structural parameters (e.g., number of vertices, degrees, etc.) instead of algebraic quantities?

share|improve this question
5  
You should tell in what terms do you want to get the bounds. –  Łukasz Grabowski Oct 21 '10 at 18:32
2  
To expand on Lukasz' comment: the upper bound is infinity, and the lower bound is zero. If the number of vertices is $n$, the upper bound is whatever you get for the complete graph, the lower bound is still zero. Maybe a good question would be, if you fix $c$, $0\lt c\lt1/2$, and ask about graphs with $n$ vertices and roughly $cn^2$ edges, what upper and lower bounds do you get as functions of $c$ and $n$. But we shouldn't have to write your question for you. –  Gerry Myerson Oct 22 '10 at 0:03
1  
As a rough count, if you've got n vertices, you've got less than $n^{n-2}$ trees. :) –  Gwyn Whieldon Oct 22 '10 at 1:28
add comment

3 Answers

up vote 5 down vote accepted

I had an email discussion with Russell Lyons a few years ago about maximizing the number of spanning trees among all graphs with a given number of vertices and edges. He had a simple argument for an upper bound of $(2e/v)^{v-1}$. There's an even simpler argument for an upper bound of $e\choose v-1$. Russell thought there was a good bound for regular graphs due to McKay.

As for lower bounds, if the graph is not connected, it has zero spanning trees, and even an $n$-vertex graph with just $n-1$ edges missing (compared to the complete graph) may not be connected. I suppose one could restrict to connected graphs and then ask for a minimum.

EDIT: Here are bibliographical details on two papers by McKay:

McKay, Brendan D., Spanning trees in regular graphs, European J. Combin. 4 (1983), no. 2, 149–160, MR 85d:05194.

McKay, Brendan D., Spanning trees in random regular graphs, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981), pp. 139–143, Univ. West Indies, Cave Hill Campus, Barbados, 1981, MR 83g:05030.

share|improve this answer
    
When $e$ is close to $v$, the bound $\binom{e}{v-1}$ is stronger. Are there any stronger upper bounds than this for the case when $e$ is small? –  David Harris Aug 11 '11 at 12:43
add comment

Thank you all for your kind answers. In my question I was specifically interested in bounds given in terms of readily available quantities like number of vertices, edges, max degree, etc. Thanks to Gerry for his references. I have also learn about other references on my own. Essentially there is a good list of bounds in

L. Feng, et al., Sharp upper bounds for the number of spanning trees of a graph, Appl. Anal. Discrete Math. 2 (2008), 255-259.

share|improve this answer
add comment

kirchhoff's theorem gives both a lower and upper bound

share|improve this answer
    
Link to statement and discussion of Kirchhoff's Matrix-Tree Theorem: en.wikipedia.org/wiki/Kirchhoff's_theorem –  Gerry Myerson Oct 22 '10 at 0:06
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.