Forest formulas of discrete Green's functions

The discrete Green's functions are the pseudoinverse (or the inverse) of the Laplacian (or its variations) of a graph. In this article, we will give combinatorial interpretations of Green's functions in terms of enumerating trees and forests in a graph that will be used to derive further formulas for several graph invariants. For example, we show that the trace of the Green's functionG ${\bf{G}}$ associated with the combinatorial Laplacian of a connected simple graphΓ ${\rm{\Gamma }}$ onn $n$ vertices satisfiesTr( G ) = ∑ λ i ≠ 01 λ i = 1 n τF 2 * , $\,\text{Tr}\,({\bf{G}})=\sum _{{\lambda }_{i}\ne 0}\frac{1}{{\lambda }_{i}}=\frac{1}{n\tau }\left|{{\mathbb{F}}}_{2}^{* }\right|,$whereλ i${\lambda }_{i}$ denotes the eigenvalues of the combinatorial Laplacian,τ $\tau $ denotes the number of spanning trees, andF 2 *${{\mathbb{F}}}_{2}^{* }$ denotes the set of rooted spanning 2‐forests inΓ ${\rm{\Gamma }}$ . We will prove forest formulas for discrete Green's functions for directed and weighted graphs and apply them to study random walks on graphs and digraphs. We derive a forest expression of the hitting time for digraphs, which gives combinatorial proofs to old and new results about hitting times, traces of discrete Green's functions, and other related quantities.