Premium
Notes on growing a tree in a graph
Author(s) -
Devroye Luc,
Dujmović Vida,
Frieze Alan,
Mehrabian Abbas,
Morin Pat,
Reed Bruce
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20828
Subject(s) - combinatorics , vertex (graph theory) , spanning tree , graph , mathematics , enhanced data rates for gsm evolution , random graph , tree (set theory) , discrete mathematics , computer science , artificial intelligence
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 .