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 条

[1] Limit laws for functions of fringe trees for binary search trees and random recursive trees
Holmgren, Cecilia
Janson, Svante
ELECTRONIC JOURNAL OF PROBABILITY, 2015, 20 : 1 - 51
[2] On the independence number of some random trees
Janson, Svante
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2020, 25 : 1 - 14
[3] The expected independent domination number of random directed rooted trees
Song, JH
Lee, CW
JOURNAL OF THE KOREAN MATHEMATICAL SOCIETY, 2004, 41 (05) : 921 - 931
[4] DOMINATION NUMBER, INDEPENDENT DOMINATION NUMBER AND 2-INDEPENDENCE NUMBER IN TREES
Dehgardi, Nasrin
Sheikholeslami, Seyed Mahmoud
Valinavaz, Mina
Aram, Hamideh
Volkmann, Lutz
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (01) : 39 - 49
[5] Domination number, independent domination number and k-independence number in trees
Cui, Qing
Zou, Xu
DISCRETE APPLIED MATHEMATICS, 2025, 366 : 176 - 184
[6] Isolation Number versus Domination Number of Trees
Lemanska, Magdalena
Jose Souto-Salorio, Maria
Dapena, Adriana
Vazquez-Araujo, Francisco J.
MATHEMATICS, 2021, 9 (12)
[7] A note on cops and robbers, independence number, domination number and diameter
Petr, Jan
Portier, Julien
Versteegen, Leo
DISCRETE MATHEMATICS, 2023, 346 (01)
[8] On the richness of the collection of subtrees in random binary search trees
Devroye, L
INFORMATION PROCESSING LETTERS, 1998, 65 (04) : 195 - 199
[9] Domination number and Laplacian eigenvalue of trees
Xue, Jie
Liu, Ruifang
Yu, Guanglong
Shu, Jinlong
LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 592 : 210 - 227
[10] Domination number and Laplacian eigenvalue of trees
Xue J.
Liu R.
Yu G.
Shu J.
Linear Algebra and Its Applications, 2020, 592 : 210 - 227

← 1 2 3 4 5 →