×

zbMATH — the first resource for mathematics

Analysis of three graph parameters for random trees. (English) Zbl 1208.05011
Summary: We consider three basic graph parameters, the node-independence number, the path node-covering number, and the size of the kernel, and study their distributional behavior for an important class of random tree models, namely the class of simply generated trees, which contains, e.g., binary trees, rooted labeled trees, and planted plane trees, as special instances. We can show for simply generated tree families that the mean and the variance of each of the three parameters under consideration behave for a randomly chosen tree of size \(n\) asymptotically \(\sim \mu n\) and \(\sim \nu n\), where the constants \(\mu \) and \(\nu \) depend on the tree family and the parameter studied. Furthermore we show for all parameters, suitably normalized, convergence in distribution to a Gaussian distributed random variable.

MSC:
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, The continuum random tree II: An overview, London Math Soc Lecture Note Ser 167 pp 23– (1991) · Zbl 0791.60008
[2] Banderier, Proceedings of formal power series and algebraic combinatorics (2004)
[3] Berge, Graphs (1985)
[4] Cho, On the asymptotic behaviour of the independence number of a random (n,n)-tree, Graphs Combinatorics 12 pp 1– (1996) · Zbl 0845.05081
[5] Drmota, Systems of functional equations, Random Struct Algorithms 10 pp 103– (1997)
[6] Drmota, Combinatorics and asymptotics on trees, Cubo 6 pp 105– (2004) · Zbl 1080.05004
[7] Flajolet, The average height of binary trees and other simple trees, J Comput Syst Sci 25 pp 171– (1982) · Zbl 0499.68027
[8] Flajolet, Singularity analysis of generating functions, SIAM J Discrete Math 3 pp 216– (1990) · Zbl 0712.05004
[9] Hwang, On convergence rates in the central limit theorems for combinatorial structures, Eur J Combinatorics 19 pp 329– (1998) · Zbl 0906.60024
[10] Meir, The expected node-independence number of random trees, Koninklijke Nederlandse Akademie van Wetenschappen. Proceedings Ser A 76 pp 335– (1973)
[11] Meir, The expected node-independence number of various types of trees, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) pp 351– (1975)
[12] Meir, On the altitude of nodes in random trees, Can J Math 30 pp 997– (1978) · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[13] Meir, Path node-covering constants for certain families of trees, Math Proc Cambridge Philos Soc 84 pp 519– (1978) · Zbl 0395.05027
[14] von Neumann, Theory of games and economic behavior (1980)
[15] Pittel, Normal convergence problem? Two moments and a recurrence may be the clues, Ann Appl Probability 9 pp 1260– (1999) · Zbl 0960.60014
[16] Vitter, Handbook of theoretical computer science pp 431– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.