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 条

[21] BOUNDS ON THE LOCATING ROMAN DOMINATION NUMBER IN TREES
Rad, Nader Jafari
Rahbani, Hadi
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2018, 38 (01) : 49 - 62
[22] On Sombor index of trees with fixed domination number
Sun, Xiaoling
Du, Jianwei
APPLIED MATHEMATICS AND COMPUTATION, 2022, 421
[23] BOUNDS ON THE LOCATING-DOMINATION NUMBER AND DIFFERENTIATING-TOTAL DOMINATION NUMBER IN TREES
Rad, Nader Jafari
Rahbani, Hadi
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2018, 38 (02) : 455 - 462
[24] THE INDEPENDENT DOMINATION NUMBER OF RANDOM GRAPH
Wang, Changping
UTILITAS MATHEMATICA, 2010, 82 : 161 - 166
[25] ON THE CONCENTRATION OF THE DOMINATION NUMBER OF THE RANDOM GRAPH
Glebov, Roman
Liebenau, Anita
Szabo, Tibor
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (03) : 1186 - 1206
[26] Extremal energies of trees with a given domination number
Xu, Kexiang
Feng, Lihua
LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 435 (10) : 2382 - 2393
[27] Independence Number and k-Trees of Graphs
Yan, Zheng
GRAPHS AND COMBINATORICS, 2017, 33 (05) : 1089 - 1093
[28] Embedding trees in graphs with independence number two
Hu, Xiaolan
Chen, Yaojun
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (04)
[29] Average Distance, Independence Number, and Spanning Trees
Mukwembi, Simon
JOURNAL OF GRAPH THEORY, 2014, 76 (03) : 194 - 199
[30] On the spectral radius of trees with given independence number
Ji, Chunyu
Lu, Mei
LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 488 : 102 - 108

← 1 2 3 4 5 →