Forest formulas of discrete Green's functions

DOI10.1002/JGT.22887MaRDI QIDQ6046689zbMATH OpenOpenAlexWikidataFDO

Authors Fan Chung, Ji Zeng

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.01324

zbMATH Keywords

treesdirected graphsrandom walks on graphsalgebraic graph theory

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Random walks on graphs (05C81)

Abstract: The discrete Green's functions are the pseudoinverse (or the inverse) of the Laplacian (or its variations) of a graph. In this paper, 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 function $mathbfG$ associated with the combinatorial Laplacian of a connected simple graph $Gamma$ on $n$ vertices satisfies $extTr(mathbfG)=su{m}_{lambd{a}_{i}eq0}frac1lambd{a}_i=frac1nau|mathbb{F}_2^{\ast }|$, where $lambd{a}_i$ denotes the eigenvalues of the combinatorial Laplacian, $au$ denotes the number of spanning trees and $mathbb{F}_2^{\ast }$ denotes the set of rooted spanning $2$-forests in $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.

Recommendations

• Discrete Green's functions and random walks on graphs
• A hitting time formula for the discrete Green's function
• Combinatorial Green's function of a graph and applications to networks
• Spanning trees and random walks on weighted graphs
• The number of spanning forests of a graph

Cites work

• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A combinatorial Laplacian with vertex weights
• A hitting time formula for the discrete Green's function
• Chung-Yau invariants and graphs with symmetric hitting times
• Commute times for a directed graph using an asymmetric Laplacian
• Discrete Green's functions
• Discrete Green's functions and random walks on graphs
• Extreme values of the stationary distribution of random walks on directed graphs
• Forest matrices around the Laplacian matrix
• Hitting time quasi-metric and its forest representation
• Maximum hitting time for random walks on graphs
• Spanning trees and random walks on weighted graphs
• The electrical resistance of a graph captures its commute and cover times
• \texttt{PageRank} and random walks on graphs

Cited in

(5)

• Application of a generalized Sherman-Morrison formula to the computation of network Green's functions and the construction of spanning trees
• Combinatorial Green's function of a graph and applications to networks
• Moore-Penrose inverse of the signless Laplacians of bipartite graphs
• Discrete Green's functions and random walks on graphs
• A hitting time formula for the discrete Green's function

This page was built for publication: Forest formulas of discrete Green's functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046689)