Discrete Green's functions for products of regular graphs

2003/09/04 by Robert B. Ellis, Ellis, Robert B.
Computer Science · Mathematics · #05C50 (Primary) 60G50 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric Topology (math.GT) #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #math.CO #math.GT #math.PR #msc:05C50 #msc:60G50

paper · pdf · doi:10.48550/arxiv.math/0309080

17 pages, 1 figure

openalex publication_date 2003/09/04 · arxiv created 2003/09/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Discrete Green's functions are the inverses or pseudo-inverses of combinatorial Laplacians. We present compact formulas for discrete Green's functions, in terms of the eigensystems of corresponding Laplacians, for products of regular graphs with or without boundary. Explicit formulas are derived for the cycle, torus, and 3-dimensional torus, as is an inductive formula for the t-dimensional torus with n vertices, from which the Green's function can be completely determined in time O(t n^2-1/tlogn). These Green's functions may be used in conjunction with diffusion-like problems on graphs such as electric potential, random walks, and chip-firing games or other balancing games.

Related

• A Hitting Time Formula for the Discrete Green's Function
• Characterization of Green's function of discrete Schrödinger operator on a finite graph by its spanning subgraphs
• Green functions on self-similar graphs and bounds for the spectrum of the Laplacian
• Discrete diffusion-type equation on regular graphs and its applications
• Green's function on lattices