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.

There's a marvelous theorem in graph theory that reduces the count of spanning trees for a graph to a computation of determinant of a naturally-defined matrix (the Laplacian matrix):

http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem

I am looking for a book proving the theorem for the following setting: $G$ is a directed graph which allows for multiple edges (which means the Laplacian might contain values other than $-1,0$ off the diagonal). In this case, the minor obtained from removing the $i$th row and column corresponds to the number of spanning tree whose root is $i$.

My usual reference for algebraic graph theory is Godsil and Royle; however, they prove the theorem for a simpler setting (or I don't understand what they do).

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Dave Perkinson has just what you are looking for:

http://people.reed.edu/~davidp/412/handouts/matrix-tree.pdf

share|improve this answer
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.