New Bounds on Domination and Independence in Graphs1

被引：0

作者：

Harant, Jochen ^{[1
]}

Mohr, Samuel ^{[1
,2
]}

机构：

[1] TU Ilmenau, Inst Math, D-98684 Ilmenau, Germany

[2] Masaryk Univ, Fac Informat, Brno 60200, Czech Republic

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2023年 / 43卷 / 03期

关键词：

undirected graph; domination number; independence number; bounds; NUMBER;

D O I：

10.7151/dmgt.2406

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value, the minimum, and the maximum of a random variable with bounded distribution.

引用

页码：809 / 824

页数：16

共 50 条

[21] Domination and independence numbers of large 2-crossing-critical graphs
Irsic, Vesna
Lekse, Marusa
Paenik, Mihael
Podlogar, Petra
Praeek, Martin
ARS MATHEMATICA CONTEMPORANEA, 2023, 23 (04)
[22] Independence and connectivity in 3-domination-critical graphs
Zhang, LZ
Tian, F
DISCRETE MATHEMATICS, 2002, 259 (1-3) : 227 - 236
[23] On k-domination and j-independence in graphs
Hansberg, Adriana
Pepper, Ryan
DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) : 1472 - 1480
[24] New upper bounds for the independence numbers of graphs with vertices in {−1, 0, 1}n and their applications to problems of the chromatic numbers of distance graphs
E. I. Ponomarenko
A. M. Raigorodskii
Mathematical Notes, 2014, 96 : 140 - 148
[25] Lower bounds for the domination number and the total domination number of direct product graphs
Mekis, Gasper
DISCRETE MATHEMATICS, 2010, 310 (23) : 3310 - 3317
[26] BOUNDS ON THE 2-DOMINATION NUMBER IN CACTUS GRAPHS
Chellali, Mustapha
OPUSCULA MATHEMATICA, 2006, 26 (01) : 5 - 12
[27] Bounds on the 2-Rainbow Domination Number of Graphs
Yunjian Wu
Nader Jafari Rad
Graphs and Combinatorics, 2013, 29 : 1125 - 1133
[28] Upper bounds for the domination number in graphs of diameter two
Meierling, Dirk
Volkmann, Lutz
UTILITAS MATHEMATICA, 2014, 93 : 267 - 277
[29] Bounds of Laplacian spectrum of graphs based on the domination number
Lu, M
Liu, HQ
Tian, F
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 402 : 390 - 396
[30] Bounds on the 2-Rainbow Domination Number of Graphs
Wu, Yunjian
Rad, Nader Jafari
GRAPHS AND COMBINATORICS, 2013, 29 (04) : 1125 - 1133

← 1 2 3 4 5 →