Premium
The structure and distances in Yule recursive trees
Author(s) -
Feng Qunqiang,
Su Chun
Publication year - 2007
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.20183
Subject(s) - mathematics , combinatorics , tree (set theory) , poisson distribution , limit (mathematics) , discrete mathematics , random tree , distribution (mathematics) , statistics , computer science , mathematical analysis , motion planning , artificial intelligence , robot
Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y t is isomorphic to a given rooted tree γ ; and then prove that the asymptotic distribution of ζ t , m , the number of the branches of size m , is the Poisson distribution with parameter λ = 1/ m . Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007