Premium
Ancestors and descendants in evolving k ‐tree models
Author(s) -
Panholzer Alois,
Seitz Georg
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20474
Subject(s) - limiting , struct , probabilistic logic , graph , combinatorics , random graph , preferential attachment , tree (set theory) , mathematics , family tree , computer science , discrete mathematics , theoretical computer science , statistics , engineering , mechanical engineering , complex network , programming language
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