ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

A note on the maximal degree in random k-trees

Funds:  Supported by the National Natural Science Foundation of China(11771418).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2020.03.010
More Information
  • Corresponding author: FENG Qiangqun(corresponding author), male, born in 1979, PhD/professor. Research field: random network. E-mail: fengqq@ustc.edu.cn
  • Received Date: 29 October 2019
  • Accepted Date: 12 January 2020
  • Rev Recd Date: 12 January 2020
  • Publish Date: 31 March 2020
    Abstract

  • Abstract

    The random variable Zn is investigated, the maximal node degree in a random k-tree at step n for k≥2.

    Abstract

    The random variable Zn is investigated, the maximal node degree in a random k-tree at step n for k≥2.
    • FullText(HTML)
  • loading
    • References(30)
  • [1]
    GAO Y. The degree distribution of random k-trees[J]. Theoretical Computer Science, 2009, 410: 688-695.
    [2]
    BEINEKE L W, PIPPERT R E. The number of labeled k-dimensional trees[J]. Journal of Combinatorial Theory,1969, 6: 200-205.
    [3]
    BODLAENDER H. A Partial k-arboretum of graphs with bounded tree width[J]. Theoretical Computer Science, 1998, 209: 1-45.
    [4]
    DRMOTA M. Random Trees[M]. Springer-Verlag, Wien, 2009.
    [5]
    SMYTHE R T, MAHMOUD H M. A survey of recursive trees. Theory of Probability and Mathematical Statistics, 1996, 51: 1-27.
    [6]
    DOROGOVTSEV S N, MENDES J F F, SAMUKHIN A N. Size-dependent degree distribution of a scale-free growing network[J]. Physical Review E, 2001, 63, 062101.
    [7]
    JANSON S. Asymptotic degree distribution in random recursive trees[J]. Random Structures and Algorithms, 2005, 26: 69-83.
    [8]
    DEVROYE L, LU J. The strong convergence of maximal degrees in uniform random recursive trees and dags[J]. Random Structures and Algorithms, 1995, 7: 1-14.
    [9]
    GOH W, SCHMUTZ E. Limit distribution for the maximum degree of a random recursive tree[J]. Journal of Computational and Applied Mathematics, 2002, 142: 61-82.
    [10]
    ADDARIO-BERRY L, ESLAVA L. High degrees in random recursive trees[J]. Random Structures and Algorithms, 2018, 52: 560-575.
    [11]
    BODINI O, DARRASSE A, HWANG H-K,et al. The connectivity-prole of random increasing k-trees[C]// Proceedings of the Workshop on Analytic Algorithmics and Combinatorics, 2010: 99-106.
    [12]
    COOPER C, FRIEZE A, UEHARA R. The height of random k-trees and related branching processes[J]. Random Structures and Algorithms, 2014, 45: 675-702.
    [13]
    COOPER C, UEHARA R. Scale free properties of random k-trees[J]. Mathematics in Computer Science, 2010, 3: 489-496.
    [14]
    DARRASSE A, HWANG H-K, SORIA M. Shape measures of random increasing k-trees[J]. Combinatorics, Probability and Computing, 2016, 25: 668-699.
    [15]
    PANHOLZER A, SEITZ G. Ancestors and descendants in evolving k-tree models[J]. Random Structures and Algorithms, 2014, 44: 465-489.
    [16]
    MORI T F. On random trees[J]. Studia Scientiarum Mathematicarum Hungarica, 2002, 39: 143-155.
    [17]
    MORI T F. The maximum degree of the Barabasi-Albert random trees[J]. Combinatorics, Probability and Computing, 2005, 14: 339-348.
    [18]
    DURRETT R. Random Graph Dynamics[M]. Cambridge: Cambridge University Press , 2007.
    [19]
    VAN DER HOFSTAD R. Random graphs and complex networks: Volume 1[M]. Cambrige: Cambrige University Press, 2016.
    [20]
    DURRETT R. Probability: Theory and Examples[M]. 4ed, Cambridge: Cambridge University Press, 2010.
    [21]
    ZHANG P, MAHMOUD H. The degree prole and weight in Apollonian networks and k-trees[J]. Advances in Applied Probability, 2016, 48: 163-175.
    [22]
    BILLINGSLEY P. Probability and Measure[M]. 3ed, New York: John Wiley, 1995.
    [23]
    BOYD D W. The sequence of radii of the Apollonian packing[J]. Mathematics of Computation, 1982, 39: 249-254.
    [24]
    ANDRADE J S, HERRMANN H J, ANDRADE R F S, et al. Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs[J]. Physical Review Letters, 2005, 94: 018702.
    [25]
    DOYE J P K, MASSEN C P. Self-similar disk packings as model spatial scale-free networks[J]. Physical Review E, 2005, 71: 016128.
    [26]
    ZHANG Z, RONG L, COMELLAS F. High-dimensional random Apollonian networks[J]. Physica A, 2006, 364: 610-618.
    [27]
    EBRAHIMZADEH E, FARCZADI L, GAO P, et al. On the longest paths and diameter in random Apollonian networks[J]. Random Structures and Algorithms, 2014, 45: 703-725.
    [28]
    COOPER C, FRIEZE A. Long paths in random Apollonian networks[J]. Internet Mathematics, 2015, 11: 308-318.
    [29]
    KOLOSSVARY I, KOMJATHY J, VAGO L. Degrees and distances in random and evolving Apollonian networks[J]. Advances in Applied Probability, 2016, 48: 865-902.
    [30]
    COLLEVECCHIO A, MEHRABIAN A, WORMALD N. (). Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees[J]. Journal of Applied Probability, 2016, 53: 846-856.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    GAO Y. The degree distribution of random k-trees[J]. Theoretical Computer Science, 2009, 410: 688-695.
    [2]
    BEINEKE L W, PIPPERT R E. The number of labeled k-dimensional trees[J]. Journal of Combinatorial Theory,1969, 6: 200-205.
    [3]
    BODLAENDER H. A Partial k-arboretum of graphs with bounded tree width[J]. Theoretical Computer Science, 1998, 209: 1-45.
    [4]
    DRMOTA M. Random Trees[M]. Springer-Verlag, Wien, 2009.
    [5]
    SMYTHE R T, MAHMOUD H M. A survey of recursive trees. Theory of Probability and Mathematical Statistics, 1996, 51: 1-27.
    [6]
    DOROGOVTSEV S N, MENDES J F F, SAMUKHIN A N. Size-dependent degree distribution of a scale-free growing network[J]. Physical Review E, 2001, 63, 062101.
    [7]
    JANSON S. Asymptotic degree distribution in random recursive trees[J]. Random Structures and Algorithms, 2005, 26: 69-83.
    [8]
    DEVROYE L, LU J. The strong convergence of maximal degrees in uniform random recursive trees and dags[J]. Random Structures and Algorithms, 1995, 7: 1-14.
    [9]
    GOH W, SCHMUTZ E. Limit distribution for the maximum degree of a random recursive tree[J]. Journal of Computational and Applied Mathematics, 2002, 142: 61-82.
    [10]
    ADDARIO-BERRY L, ESLAVA L. High degrees in random recursive trees[J]. Random Structures and Algorithms, 2018, 52: 560-575.
    [11]
    BODINI O, DARRASSE A, HWANG H-K,et al. The connectivity-prole of random increasing k-trees[C]// Proceedings of the Workshop on Analytic Algorithmics and Combinatorics, 2010: 99-106.
    [12]
    COOPER C, FRIEZE A, UEHARA R. The height of random k-trees and related branching processes[J]. Random Structures and Algorithms, 2014, 45: 675-702.
    [13]
    COOPER C, UEHARA R. Scale free properties of random k-trees[J]. Mathematics in Computer Science, 2010, 3: 489-496.
    [14]
    DARRASSE A, HWANG H-K, SORIA M. Shape measures of random increasing k-trees[J]. Combinatorics, Probability and Computing, 2016, 25: 668-699.
    [15]
    PANHOLZER A, SEITZ G. Ancestors and descendants in evolving k-tree models[J]. Random Structures and Algorithms, 2014, 44: 465-489.
    [16]
    MORI T F. On random trees[J]. Studia Scientiarum Mathematicarum Hungarica, 2002, 39: 143-155.
    [17]
    MORI T F. The maximum degree of the Barabasi-Albert random trees[J]. Combinatorics, Probability and Computing, 2005, 14: 339-348.
    [18]
    DURRETT R. Random Graph Dynamics[M]. Cambridge: Cambridge University Press , 2007.
    [19]
    VAN DER HOFSTAD R. Random graphs and complex networks: Volume 1[M]. Cambrige: Cambrige University Press, 2016.
    [20]
    DURRETT R. Probability: Theory and Examples[M]. 4ed, Cambridge: Cambridge University Press, 2010.
    [21]
    ZHANG P, MAHMOUD H. The degree prole and weight in Apollonian networks and k-trees[J]. Advances in Applied Probability, 2016, 48: 163-175.
    [22]
    BILLINGSLEY P. Probability and Measure[M]. 3ed, New York: John Wiley, 1995.
    [23]
    BOYD D W. The sequence of radii of the Apollonian packing[J]. Mathematics of Computation, 1982, 39: 249-254.
    [24]
    ANDRADE J S, HERRMANN H J, ANDRADE R F S, et al. Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs[J]. Physical Review Letters, 2005, 94: 018702.
    [25]
    DOYE J P K, MASSEN C P. Self-similar disk packings as model spatial scale-free networks[J]. Physical Review E, 2005, 71: 016128.
    [26]
    ZHANG Z, RONG L, COMELLAS F. High-dimensional random Apollonian networks[J]. Physica A, 2006, 364: 610-618.
    [27]
    EBRAHIMZADEH E, FARCZADI L, GAO P, et al. On the longest paths and diameter in random Apollonian networks[J]. Random Structures and Algorithms, 2014, 45: 703-725.
    [28]
    COOPER C, FRIEZE A. Long paths in random Apollonian networks[J]. Internet Mathematics, 2015, 11: 308-318.
    [29]
    KOLOSSVARY I, KOMJATHY J, VAGO L. Degrees and distances in random and evolving Apollonian networks[J]. Advances in Applied Probability, 2016, 48: 865-902.
    [30]
    COLLEVECCHIO A, MEHRABIAN A, WORMALD N. (). Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees[J]. Journal of Applied Probability, 2016, 53: 846-856.)
    Recommended articles
    TrendMD
    Volume 50 Issue 3 page: 328-334
    Cover

    Article Metrics

    Article views (59) PDF downloads(92)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return