Forest formulas of discrete Green's functions

DOI10.1002/JGT.22887zbMATH Open1522.05158arXiv2109.01324OpenAlexW3197955939WikidataQ114236115 ScholiaQ114236115MaRDI QIDQ6046689FDOQ6046689

Authors: Fan Chung, Ji Zeng 

Publication date: 6 October 2023

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• 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
• Application of a generalized Sherman-Morrison formula to the computation of network Green's functions and the construction of spanning trees

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)