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

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