Generating Functions of Random Walks on Graphs

2004/04/26 by Vadim Kostrykin, Kostrykin, Vadim, Robert Schrader +1
Computer Science · Mathematics · Physics and Astronomy · #05A15 #34B45 #60G50 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #math-ph #math.CO #math.MP #msc:05A15 #msc:34B45 #msc:60G50

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

Uses epic and eepic styles

arxiv created 2004/04/26 · openalex publication_date 2004/04/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The article provides an explicit algebraic expression for the generating function of walks on graphs. Its proof is based on the scattering theory for the differential Laplace operator on non-compact graphs.

Citations

• The generalized star product and the factorization of scattering matrices on graphs
• Some Open Questions about Random Walks, Involutions, Limiting Distributions, and Generating Functions

Related

• Biased random walks on random graphs
• Conditions for Equivalence of Random Interlacements and Random Walk Reflected off of Infinity
• Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph
• A note on the Martin boundary of the simple random walk on an example of directed graph
• Simple random walk on distance-regular graphs