Premium
The Wiener Index of simply generated random trees
Author(s) -
Janson Svante
Publication year - 2003
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.10074
Subject(s) - mathematics , brownian excursion , random tree , wiener index , brownian motion , reflected brownian motion , tree (set theory) , limit (mathematics) , combinatorics , statistical physics , mathematical analysis , statistics , geometric brownian motion , diffusion process , physics , graph , knowledge management , innovation diffusion , motion planning , artificial intelligence , computer science , robot
Asymptotics are obtained for the mean, variance, and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a critical Galton–Watson tree). We also establish a joint asymptotic distribution of the Wiener index and the internal path length, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion. The methods include both Aldous' theory of the continuum random tree and analysis of generating functions. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 337–358, 2003