Vizing's conjecture for graphs with domination number 3-a new proof

被引：0
|
作者：
Bresar, Bostjan [1 ,2 ]
机构：
[1] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia
[2] Inst Math Phys & Mech, Ljubljana, Slovenia
来源：
ELECTRONIC JOURNAL OF COMBINATORICS | 2015年 / 22卷 / 03期
关键词：
Cartesian product; domination; Vizing's conjecture;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this note we use a new, transparent approach to prove Vizing's conjecture for graphs with domination number 3; that is, we prove that for any graph G with gamma(G) = 3 and an arbitrary graph H, gamma(G rectangle H) >= 3 gamma(H).
引用
收藏
页数：8
相关论文
共 15 条
  • [1] Domination in the hierarchical product and Vizing's conjecture
    Anderson, S. E.
    Nagpal, S.
    Wash, K.
    DISCRETE MATHEMATICS, 2018, 341 (01) : 20 - 24
  • [2] Vizing's conjecture for chordal graphs
    Aharoni, Ron
    Szabo, Tibor
    DISCRETE MATHEMATICS, 2009, 309 (06) : 1766 - 1768
  • [3] Partial product of graphs and Vizing's conjecture
    Gonzalez Yero, Ismael
    ARS MATHEMATICA CONTEMPORANEA, 2015, 9 (01) : 19 - 25
  • [4] A 3/4-approximation of Vizing's conjecture for claw-free graphs
    Bresar, Bostjan
    Henning, Michael A.
    DISCRETE APPLIED MATHEMATICS, 2020, 284 : 416 - 422
  • [5] Proof of a conjecture on k-tuple domination in graphs
    Xu, Guangjun
    Kang, Liying
    Shan, Erfang
    Yan, Hong
    APPLIED MATHEMATICS LETTERS, 2008, 21 (03) : 287 - 290
  • [6] A NEW FRAMEWORK TO APPROACH VIZING'S CONJECTURE
    Bresar, Bostjan
    Hartnell, Bert L.
    Henning, Michael A.
    Kuenzel, Kirsti
    Rall, Douglas F.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (03) : 749 - 762
  • [7] DOMINATION GAME: A PROOF OF THE 3/5-CONJECTURE FOR GRAPHS WITH MINIMUM DEGREE AT LEAST TWO
    Henning, Michael A.
    Kinnersley, William B.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (01) : 20 - 35
  • [8] A NEW BOUND ON THE DOMINATION NUMBER OF CONNECTED CUBIC GRAPHS
    Kostochka, A., V
    Stocker, C.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2009, 6 : 465 - 504
  • [9] A conjecture on the lower bound of the signed edge domination number of 2-connected graphs
    Feng, Xing
    Ge, Jun
    DISCRETE APPLIED MATHEMATICS, 2021, 302 : 42 - 45
  • [10] Perfect Roman {3}-Domination in Graphs: Complexity and Bound of Perfect Roman {3}-Domination Number of Trees
    Almulhim, Ahlam
    JOURNAL OF MATHEMATICS, 2024, 2024 (01)
12