Ancestors and descendants in evolving k‐tree models1. Issue 4 (28th November 2012)

• Record Type: Journal Article
• Authors: Panholzer, Alois; Seitz, Georg
• Is Part Of: Random structures & algorithms. Volume 44:Issue 4(2014)
• Page Start: 465
• Page End: 489
• Publication Date: 2012-11-28
• Subjects: increasing k‐trees -- ancestors -- descendants -- limiting distributions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20474
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider several random graph models based on k ‐trees, which can be generated by applying the probabilistic growth rules "uniform attachment", "preferential attachment", or a "saturation"‐rule, respectively, but which also can be described in a combinatorial way. For all of these models we study the number of ancestors and the number of descendants of nodes in the graph by carrying out a precise analysis which leads to exact and limiting distributional results. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 465–489, 2014