×

zbMATH — the first resource for mathematics

The degree profile in some classes of random graphs that generalize recursive trees. (English) Zbl 1315.60012
Summary: We study the degree profile for a number of classes of random graphs that arise as generalizations of recursive trees, including random circuits and random recursive trees endowed with the power of choice. We investigate the distribution of the degrees of nodes that appear in various stages of the insertion process in each of these graph types. For these classes, we will see phase transitions in degrees depending on the stage – early stages are associated with normal distributions, intermediate stages are associated with the Poisson distribution and in the late stages the degrees become degenerate.

MSC:
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
05A05 Permutations, words, matrices
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arya, S; Golin, M; Mehlhorn, K, On the expected depth of random circuits, Comb Probab Comput, 8, 209-228, (1999) · Zbl 0941.68001
[2] Bergeron, F; Flajolet, P; Salvy, B, Varieties of increasing trees, 24-48, (1992), Berlin
[3] D’Souza, R; Krapivsky, P; Moore, C, The power of choice in growing trees, Eur Phys J B, 59, 535-543, (2007) · Zbl 1189.05157
[4] Devroye, L; Janson, S, Long and short paths in uniform random recur sive dags, Ark Mat, 49, 61-77, (2011) · Zbl 1230.60092
[5] Díaz J, Serna M, Spirakis P, Toran J (1994) On the expected depth of Boolean circuits. Report LSI-7-R, Department de Linguatges i Systemes. Universidad Politécnica Catalunya, Barcelona · Zbl 1162.68024
[6] Feng, Q; Mahmoud, H; Panholzer, A, The degree distribution of random \(k\)-trees, Theor Comput Sci, 60, 319-343, (2008) · Zbl 1332.68038
[7] Gao, Y, The degree distribution of random \(k\)-trees, Theor Comput Sci, 410, 688-695, (2009) · Zbl 1162.68024
[8] Janson, S, Asymptotic degree distribution in random recursive trees, Random Struct Algorithms, 26, 69-83, (2005) · Zbl 1059.05094
[9] Kuba, M; Panholzer, A, On the degree distribution of the nodes in increasing trees, J Comb Theory Ser A, 114, 597-618, (2007) · Zbl 1116.05020
[10] Mahmoud, H, The power of choice in the construction of recursive trees, Methodol Comput Appl Probab, 12, 763-773, (2010) · Zbl 1209.05227
[11] Mahmoud, H; Smythe, R, Asymptotic joint normality of outdegrees of nodes in random recursive trees, Random Struct Algorithms, 3, 255-266, (1992) · Zbl 0767.05086
[12] Panholzer A, Seitz G (2010) Ordered increasin \(k\)-trees: introduction and analysis of preferential attachment network model. In: Discrete mathematics and theoretical computer science. DMTC Proc. AM, pp 549-564 · Zbl 1355.05227
[13] Seitz G (2011) Analysis of various parameters in labelled trees and tree-like structures. PhD Dissertation, Vienna University of Technology, Austria · Zbl 1059.05094
[14] Smythe, R; Mahmoud, H, A survey of recursive trees, Theory Probab Math Stat, 51, 1-27, (1994) · Zbl 0933.05038
[15] Tsukiji, T; Mahmoud, H, A limit law for outputs in random circuits, Algorithmica, 31, 403-412, (2001) · Zbl 0989.68107
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.