Notes on growing a tree in a graph
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.
|Keywords||cheeger constant, first-passage percolation, graph degeneracy, graph genus, planar graphs, random spanning tree, treewidth|
|Journal||Random Structures and Algorithms|
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