Matrix-Forest Theorems

Details Matrix-Forest Theorems Matrix-Forest Theorems

2006-02-25

arxiv.org/abs/math/0602575v1

Mathematics

Combinatorics

Unpublished manuscript (1995); 10 pages

Scientific paper

The Laplacian matrix of a graph G is L(G)=D(G)-A(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees. According to the Matrix-Tree Theorem, the number of spanning trees in G is equal to any cofactor of an entry of L(G). A rooted forest is a union of disjoint rooted trees. We consider the matrix W(G)=I+L(G) and prove that the (i,j)-cofactor of W(G) is equal to the number of spanning rooted forests of G, in which the vertices i and j belong to the same tree rooted at i. The determinant of W(G) equals the total number of spanning rooted forests, therefore the (i,j)-entry of the matrix W^{-1}(G) can be considered as a measure of relative ''forest-accessibility'' of the vertex i from j (or j from i). These results follow from somewhat more general theorems we prove, which concern weighted multigraphs. The analogous theorems for (multi)digraphs are established. These results provide a graph-theoretic interpretation for the adjugate to the Laplacian characteristic matrix.

Affiliated with

Also associated with

No associations

Rating

Matrix-Forest Theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Matrix-Forest Theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matrix-Forest Theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-730348