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 条
  • [1] Roman domination in direct product graphs and rooted product graphs1
    Martinez, Abel Cabrera
    Peterin, Iztok
    Yero, Ismael G.
    AIMS MATHEMATICS, 2021, 6 (10): : 11084 - 11096
  • [2] New Bounds on the Double Total Domination Number of Graphs
    A. Cabrera-Martínez
    F. A. Hernández-Mira
    Bulletin of the Malaysian Mathematical Sciences Society, 2022, 45 : 443 - 453
  • [3] New Bounds on the Double Total Domination Number of Graphs
    Cabrera-Martinez, A.
    Hernandez-Mira, F. A.
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2022, 45 (01) : 443 - 453
  • [4] Bounds on Domination Parameters in Graphs: A Brief Survey
    HENNING, M. I. C. H. A. E. L. A.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (03) : 665 - 708
  • [5] A note on domination and independence-domination numbers of graphs
    Milanic, Martin
    ARS MATHEMATICA CONTEMPORANEA, 2013, 6 (01) : 89 - 97
  • [6] Independence and k-domination in graphs
    Hansberg, Adriana
    Meierling, Dirk
    Volkmann, Lutz
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (05) : 905 - 915
  • [7] CHARACTERIZATION OF GRAPHS WITH EQUAL DOMINATION NUMBERS AND INDEPENDENCE NUMBERS
    Jou, Min-Jen
    TAIWANESE JOURNAL OF MATHEMATICS, 2010, 14 (04): : 1537 - 1542
  • [8] BOUNDS ON THE DOMINATION NUMBER OF PERMUTATION GRAPHS
    Gu, Weizhen
    Wash, Kirsti
    JOURNAL OF INTERCONNECTION NETWORKS, 2009, 10 (03) : 205 - 217
  • [9] On the Bounds of the Domination Numbers of Glued Graphs
    Sripratak, Piyashat
    Panma, Sayan
    THAI JOURNAL OF MATHEMATICS, 2021, 19 (04): : 1719 - 1728
  • [10] Bounds on the domination number of Kneser graphs
    Ostergard, Patric R. J.
    Shao, Zehui
    Xu, Xiaodong
    ARS MATHEMATICA CONTEMPORANEA, 2015, 9 (02) : 197 - 205
12345