Welcome to MathOverflow

Question

3

2

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?

edited Nov 19 2010 at 1:04

asked Oct 21 2010 at 17:57

Simone Severini
557●2●9

5

You should tell in what terms do you want to get the bounds. – Łukasz Grabowski Oct 21 2010 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 2010 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 2010 at 1:28

Gerry Myerson · Accepted Answer · 2010-10-22 01:51:11Z UTC

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.

Simone Severini · Answer 2 · 2010-11-19 00:57:31Z UTC

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.

ohai · Answer 3 · 2010-10-21 18:01:40Z UTC

1

kirchhoff's theorem gives both a lower and upper bound

answered Oct 21 2010 at 18:01

ohai
273●2●7

Link to statement and discussion of Kirchhoff's Matrix-Tree Theorem: en.wikipedia.org/wiki/Kirchhoff's_theorem – Gerry Myerson Oct 22 2010 at 0:06

Number of spanning trees: bounds from structural parameters

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.