We study the height of a spanning tree T of a graph G obtained by starting with a single vertex of G and repeatedly selecting, uniformly at random, an edge of G with exactly one endpoint in T and adding this edge to T.

cheeger constant, first-passage percolation, graph degeneracy, graph genus, planar graphs, random spanning tree, treewidth
Random Structures and Algorithms
School of Computer Science

Devroye, L. (Luc), Dujmović, V, Frieze, A. (Alan), Mehrabian, A. (Abbas), Morin, P, & Reed, B. (Bruce). (2018). Notes on growing a tree in a graph. Random Structures and Algorithms. doi:10.1002/rsa.20828