Parameters of a Random Rooted Tree
We study the distribution of three tree parameters, namely, the independence number, the domination number, and the total domination number in the conditioned Galton-Watson model. We show that these tree parameters are asymptotically normal as the order of the tree tends to infinity. Our method is based on the analysis of bottom-up algorithms that can compute these quantities for trees. From these algorithms, we can construct tree additive functionals whose toll functions are almost local. We then apply a recent result on the central limit theorem for additive functionals with almost local toll functions. Furthermore, while addressing an open problem in a recent paper by Janson, we show, under a mild condition on the moments of the offspring distribution for the Galton-Watson tree, that the number of copies of any fixed rooted plane tree as general subtrees has a mean and variance linear in the size of the random tree.