zbMATH — the first resource for mathematics

The random walk construction of uniform spanning trees and uniform labelled trees. (English) Zbl 0717.05028
The author uses a random walk on a finite connected graph G to construct a uniform random spanning tree on G. The theory of random walks is used to study the proportion of leaves, the distribution of degrees, and the diameter of a uniform random spanning tree of a graph. The random-walk Markov chain is defined on the vertices of an n-vertex, connected graph G having transition probabilities: at vertex v, the probability of moving along edge \((v,v')\) (to go to vertex \(v')\) is \(1/d_ v\) where \(d_ v\) is the degree of v. Note that with probability 1, all vertices will be visited at least once in finite time. Using this Markov chain starting from a given vertex, mark the edge used to arrive the first time at vertex v, for each v. The set of marked edges is proved to be a uniform random spanning tree.
Reviewer: A.Tucker

05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI