Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$.

There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to me) is that if $C_n^2$ denotes the square of a cycle, then

$$\tau(G) = n^2 f_n$$

where $f_n$ is the $n$'th Fibonacci number.

What I am wondering is if there are any known applications (practical and theoretical) of knowing $\tau(G)$ for certain graphs?

share|improve this question
    
Did you find out any?Even Im searching for one.. –  user30645 May 4 '12 at 18:56
    
Yeah there are some applications! I'll write an answer soon –  Jernej May 9 '12 at 10:07
1  
This is related to resistances in circuits, but I don't remember the exact statement. –  Qiaochu Yuan Jul 5 '12 at 15:42

3 Answers 3

By the Matrix Tree Theorem $\tau(G)$ equals the cofactor of the graph Laplacian of $G$. Usually the Matrix Tree Theorem is applied to compute $\tau(G)$, but it might be also used in the other direction, namely, to compute the cofactor of the graph Laplacian.

Here is one example for this: The currently best algorithm for realizing planar 3-connected graphs as 3d polytopes with small integer coordinates, produces first an embedding with rational coordinates that will be scaled to integrality. The scaling factor can be deduced from the cofactor of the Laplacian of the graph of the polytope. In order to bound the grid size of the embedding one uses a bound on the maximal number of spanning trees in planar graphs.

See Small Grid Embeddings of 3-polytopes by Ribó, Rote, and Schulz.

share|improve this answer

Belief propagation on random fields, a technique used to calculate the marginals of a distribution in applications such as image processing, comes in handy when the graph represented by the random field is not complicated (with less cycles, average degrees, etc.). So far, we know that the solutions from belief propagation are exact if the underlying graph is a tree (not loopy).

I have seen some work that try to reduce complex graphs into their spanning trees to do exact inference while keeping the important properties of the original graph. So the number of spanning trees may tell something about the likelihood of a certain random field being able to be efficiently sparsified for approximate marginal solutions.

share|improve this answer

As Qiaochu Yuan mentions in his comment, the number of spanning trees has relevance in electrical network theory, which again have implications for random walks in graphs. There is some material in Chapter 9 of http://www.student.dtu.dk/~s082951/01227/01227-GraphTheory.pdf

share|improve this answer

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.