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.

Additional Metadata
Keywords cheeger constant, first-passage percolation, graph degeneracy, graph genus, planar graphs, random spanning tree, treewidth
Persistent URL dx.doi.org/10.1002/rsa.20828
Journal Random Structures and Algorithms
Citation
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