|
|||||
|
|
Notes on growing a tree in a graph |
|
| Authors: | Luc Devroye Vida Dujmovi&#x; Alan Frieze Abbas Mehrabian Pat Morin Bruce Reed |
| Institution: | Luc Devroye,Vida Dujmovi?,Alan Frieze,Abbas Mehrabian,Pat Morin,Bruce Reed |
| Abstract: | 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 |