Notes on growing a tree in a graph. Issue 2 (18th December 2018)

• Record Type: Journal Article
• Authors: Devroye, Luc; Dujmović, Vida; Frieze, Alan; Mehrabian, Abbas; Morin, Pat; Reed, Bruce
• Is Part Of: Random structures & algorithms. Volume 55:Issue 2(2019)
• Page Start: 290
• Page End: 312
• Publication Date: 2018-12-18
• Subjects: cheeger constant -- first‐passage percolation -- graph degeneracy -- graph genus -- planar graphs -- random spanning tree -- treewidth; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20828
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .