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 条

[11] Connected Domination Number and a New Invariant in Graphs with Independence Number Three
Bercov, Vladimir
COMPUTER SCIENCE JOURNAL OF MOLDOVA, 2021, 29 (01) : 96 - 104
[12] New lower bounds for the independence numbers of distance graphs with vertices in {−1, 0, 1}n
V. F. Moskva
A. M. Raigorodskii
Mathematical Notes, 2011, 89 : 307 - 308
[13] NEW LOWER BOUNDS FOR THE INDEPENDENCE NUMBER OF SPARSE GRAPHS AND HYPERGRAPHS
Dutta, Kunal
Mubayi, Dhruv
Subramanian, C. R.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 1134 - 1147
[14] On the independence transversal total domination number of graphs
Cabrera Martinez, Abel
Sigarreta Almira, Jose M.
Yero, Ismael G.
DISCRETE APPLIED MATHEMATICS, 2017, 219 : 65 - 73
[15] Graphs with equal Grundy domination and independence number
Bacso, Gabor
Bresar, Bostjan
Kuenzel, Kirsti
Rall, Douglas F.
DISCRETE OPTIMIZATION, 2023, 48
[16] Some bounds for the captive domination number of graphs
Shaveisi, Farzad
Moshtagh, Hossein
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (08)
[17] New Lower Bounds for the Independence Numbers of Distance Graphs with Vertices in {-1,0,1}n
Moskva, V. F.
Raigorodskii, A. M.
MATHEMATICAL NOTES, 2011, 89 (1-2) : 307 - 308
[18] Unified bounds for the independence number of graphs
Zhou, Jiang
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2025, 77 (01): : 97 - 117
[19] On upper bounds for multiple domination numbers of graphs
Przybylo, Jakub
DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2758 - 2763
[20] Bounds of the 2-domination number of graphs
Blidia, Mostafa
Chellali, Mustapha
Volkmann, Lutz
UTILITAS MATHEMATICA, 2006, 71 : 209 - 216

← 1 2 3 4 5 →