Matrix-Forest Theorems
read the original abstract
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 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 also established. These results provide a graph-theoretic interpretation for the adjugate to the Laplacian characteristic matrix.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
The symmetrized determinant is #P-hard over polynomial-sized algebras and its polynomial family is VNP-complete in both non-commutative and commutative matrix algebra settings.
-
On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
Symmetrized determinant shown to have analogous principal minor expansion and to be #P-hard and VNP-complete over suitable algebras.
-
Fast Estimation for Forest Matrix of Signed Graphs
Presents signed forest matrix theorem and GSCF/FMDE algorithms achieving O(n) forest generation and O(ln) diagonal estimation for signed graphs up to 20M nodes.
-
Efficient Computation for Diagonal of Forest Matrix via Variance-Reduced Forest Sampling
New variance-reduced sampling algorithms SCF, SCFV, and SCFV+ compute forest matrix diagonals more efficiently than Laplacian solvers with error guarantees and linear time in nodes for both undirected and directed graphs.
-
The number of rooted forests in circulant graphs
Explicit formulas via Chebyshev polynomials for rooted spanning forests in circulant graphs C_n(s1..sk) and C_2n, with f_G(n)=p a(n)^2 and asymptotic via Mahler measure of associated Laurent polynomial.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.