Random Selection of Spanning Trees on Graphs

Sergio Luis Pérez-Pérez, Guillermo Benito Morales-Luna, Feliú Davino Sagols-Troncoso


Random selection of spanning trees on graphs has been treated extensively in technical literature. Popular randomized algorithms have time complexity varying from to , where  is the order of a graph, namely, the number of vertices. In this work, we introduce effective and efficient procedures to select spanning trees using random walks with the purpose to balance the diame­ter of the selected tree, the valencies of its inner vertices, and the number of leaves at its yield. We describe several ways to form transition matrices of Markov chains in terms ofprobability distributions on the neighborhood of any visited vertex along the random walk.


Random spanning trees, random walks on graphs, transition matrices in Markov chains, probability distributions on neighborhoods of vertices.

Full Text: PDF (Spanish)