A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees

被引：4
|
作者：
Fuchs, Michael [1 ]
Holmgren, Cecilia [2 ]
Mitsche, Dieter [3 ]
Neininger, Ralph [4 ]
机构：
[1] Natl Chengchi Univ, Dept Math Sci, Taipei, Taiwan
[2] Uppsala Univ, Dept Math, Uppsala, Sweden
[3] Univ Lyon, Univ Jean Monnet, Inst Camille Jordan UMR 5208, Lyon, France
[4] Goethe Univ Frankfurt, Inst Math, Frankfurt, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 2021年 / 292卷
关键词：
Independence number; Domination number; Clique cover number; Random recursive trees; Random binary search trees; Fringe trees; Central limit laws; LIMIT LAWS; ALGORITHMS; SETS;
D O I：
10.1016/j.dam.2020.12.013
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We identify the mean growth of the independence number of random binary search trees and random recursive trees and show normal fluctuations around their means. Similarly we also show normal limit laws for the domination number and variations of it for these two cases of random tree models. Our results are an application of a recent general theorem of Holmgren and Janson on fringe trees in these two random tree models. (C) 2020 Published by Elsevier B.V.
引用
收藏
页码：64 / 71
页数：8
相关论文
共 50 条
  • [31] Independence Number and k-Trees of Graphs
    Zheng Yan
    Graphs and Combinatorics, 2017, 33 : 1089 - 1093
  • [32] Minimizing the Laplacian eigenvalues for trees with given domination number
    Feng, Lihua
    Yu, Guihai
    Li, Qiao
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 419 (2-3) : 648 - 655
  • [33] Further results on the total Italian domination number of trees
    Cabrera-Martinez, Abel
    Conchado Peiro, Andrea
    Manuel Rueda-Vazquez, Juan
    AIMS MATHEMATICS, 2023, 8 (05): : 10654 - 10664
  • [34] Extremal trees for the Randic index with given domination number
    Bermudo, Sergio
    Napoles, Juan E.
    Rada, Juan
    APPLIED MATHEMATICS AND COMPUTATION, 2020, 375
  • [35] On extremal Zagreb indices of trees with given domination number
    Borovicanin, Bojana
    Furtula, Boris
    APPLIED MATHEMATICS AND COMPUTATION, 2016, 279 : 208 - 218
  • [36] On the Laplacian spectral radii of trees with given domination number
    He, Chang-Xiang
    Shan, Hai-Ying
    Wu, Bao-Feng
    UTILITAS MATHEMATICA, 2014, 93 : 171 - 177
  • [37] On the eccentric connectivity index of trees with given domination number
    Zhou, Ting
    Miao, Lianying
    Lin, Zhen
    Song, Wenyao
    DISCRETE APPLIED MATHEMATICS, 2025, 360 : 512 - 519
  • [38] ON THE MATCHING NUMBER AND THE INDEPENDENCE NUMBER OF A RANDOM INDUCED SUBHYPERGRAPH OF A HYPERGRAPH
    Lee, Sang June
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2018, 55 (05) : 1523 - 1528
  • [39] The height of depth-weighted random recursive trees
    Leckey, Kevin
    Mitsche, Dieter
    Wormald, Nick
    RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (03) : 851 - 866
  • [40] Depth of vertices with high degree in random recursive trees
    Eslava, Laura
    ALEA-LATIN AMERICAN JOURNAL OF PROBABILITY AND MATHEMATICAL STATISTICS, 2022, 19 (01): : 839 - 857
12345