Ancestors and descendants in evolving k‐tree models1. Issue 4 (28th November 2012) - Panholzer, Alois; Seitz, Georg
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