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 条
  • [41] BRANCHES IN RANDOM RECURSIVE k-ARY TREES
    Javanian, M.
    Vahidi-Asl, M. Q.
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2012, 38 (02) : 323 - 331
  • [42] Extremal Trees for the General Randić Index with a Given Domination Number
    Chang Liu
    Zimo Yan
    Jianping Li
    Bulletin of the Malaysian Mathematical Sciences Society, 2022, 45 : 767 - 792
  • [43] Extremal Trees for the General Randic Index with a Given Domination Number
    Liu, Chang
    Yan, Zimo
    Li, Jianping
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2022, 45 (02) : 767 - 792
  • [44] Permanental Bounds of the Laplacian Matrix of Trees with Given Domination Number
    Xianya Geng
    Shuna Hu
    Shuchao Li
    Graphs and Combinatorics, 2015, 31 : 1423 - 1436
  • [45] Permanental Bounds of the Laplacian Matrix of Trees with Given Domination Number
    Geng, Xianya
    Hu, Shuna
    Li, Shuchao
    GRAPHS AND COMBINATORICS, 2015, 31 (05) : 1423 - 1436
  • [46] ON MULTIPLICATIVE SUM ZAGREB INDEX OF TREES WITH FIXED DOMINATION NUMBER
    Sun, Xiaoling
    Gao, Yubin
    Du, Jianwei
    JOURNAL OF MATHEMATICAL INEQUALITIES, 2023, 17 (01): : 83 - 98
  • [47] On maximum Zagreb connection indices for trees with fixed domination number
    Raza, Zahid
    Akhter, Shehnaz
    CHAOS SOLITONS & FRACTALS, 2023, 169
  • [48] On extremal multiplicative Zagreb indices of trees with given domination number
    Wang, Shaohui
    Wang, Chunxiang
    Liu, Jia-Bao
    APPLIED MATHEMATICS AND COMPUTATION, 2018, 332 : 338 - 350
  • [49] Estimation of the Domination Number in Sparse Random Graphs and Applications
    Nehez, Martin
    Bernat, Dusan
    Lelovsky, Marek
    PROCEEDINGS OF THE FIFTH EUROPEAN CONFERENCE ON THE ENGINEERING OF COMPUTER-BASED SYSTEMS (ECBS 2017), 2017,
  • [50] The Domination Number of On-line Social Networks and Random Geometric Graphs
    Bonato, Anthony
    Lozier, Marc
    Mitsche, Dieter
    Perez-Gimenez, Xavier
    Pralat, Pawel
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015), 2015, 9076 : 150 - 163
12345