Premium
The distribution of nodes of given degree in random trees
Author(s) -
Drmota Michael,
Gittenberger Bernhard
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199907)31:3<227::aid-jgt6>3.0.co;2-6
Subject(s) - mathematics , combinatorics , degree (music) , distribution (mathematics) , discrete mathematics , mathematical analysis , acoustics , physics
Abstract Let n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ μ k n and variance ∼ σ 2 kn with positive constants μ k and σ k . Besides, the asymptotic behavior of μ k and σ k for k → ∞ as well as the corresponding multivariate distributions are derived. Furthermore, similar results can be proved for plane trees, for labeled trees, and for forests. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 227–253, 1999