Premium
The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
Author(s) -
Janson Svante
Publication year - 1995
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.3240070406
Subject(s) - spanning tree , mathematics , combinatorics , discrete mathematics , minimum spanning tree , random graph , graph , random tree , limit (mathematics) , tree (set theory) , computer science , mathematical analysis , motion planning , artificial intelligence , robot
Abstract The minimal weight of a spanning tree in a complete graph K n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.