2
$\begingroup$

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?

  • 0
    Did you find out any?Even Im searching for one..2012-05-04
  • 0
    Yeah there are some applications! I'll write an answer soon2012-05-09
  • 1
    This is related to resistances in circuits, but I don't remember the exact statement.2012-07-05

3 Answers 3