Premium
A random tree model associated with random graphs
Author(s) -
Aldous David
Publication year - 1990
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.3240010402
Subject(s) - mathematics , combinatorics , random graph , vertex (graph theory) , spanning tree , tree (set theory) , random tree , enhanced data rates for gsm evolution , discrete mathematics , random regular graph , degree distribution , graph , chordal graph , 1 planar graph , computer science , complex network , telecommunications , motion planning , artificial intelligence , robot
Grow a tree on n vertices by starting with no edges and successively adding an edge chosen uniformly from the set of possible edges whose addition would not create a cycle. This process is closely related to the classical random graph process. We describe the asymptotic structure of the tree, as seen locally from a given vertex. In particular, we give an explicit expression for the asymptotic degree distribution. Our results an be applied to study the random minimum‐weight spanning tree question, when the edge‐weight distribution is allowed to vary almost arbitrarily with n .