Vizing's conjecture for chordal graphs

被引：7
|
作者：
Aharoni, Ron [2 ]
Szabo, Tibor [1 ]
机构：
[1] ETH, Dept Comp Sci, Zurich, Switzerland
[2] Technion Israel Inst Technol, Dept Math, IL-32000 Haifa, Israel
来源：
DISCRETE MATHEMATICS | 2009年 / 309卷 / 06期
关键词：
Graph theory; Domination; Vizing's conjecture; NUMBER;
D O I：
10.1016/j.disc.2008.02.025
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Vizing conjectured that gamma (G square H) >= gamma (G) gamma (H) for every pair G, H of graphs, where "square" is the Cartesian product, and gamma (G) the domination number of the graph G. Denote by gamma(i) (G) the maximum, over all independent sets I in G, of the minimal number of vertices needed to dominate I. We prove that gamma(G square H) >= gamma(i)(G)gamma(H). Since for chordal graphs gamma(i) = gamma, this proves Vizing's conjecture when G is chordal. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：1766 / 1768
页数：3
相关论文
共 50 条
  • [1] Partial product of graphs and Vizing's conjecture
    Gonzalez Yero, Ismael
    ARS MATHEMATICA CONTEMPORANEA, 2015, 9 (01) : 19 - 25
  • [2] Vizing's conjecture for graphs with domination number 3-a new proof
    Bresar, Bostjan
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (03)
  • [3] A 3/4-approximation of Vizing's conjecture for claw-free graphs
    Bresar, Bostjan
    Henning, Michael A.
    DISCRETE APPLIED MATHEMATICS, 2020, 284 : 416 - 422
  • [4] Fair Reception and Vizing's Conjecture
    Bresar, Bostjan
    Rall, Douglas F.
    JOURNAL OF GRAPH THEORY, 2009, 61 (01) : 45 - 54
  • [5] Vizing's conjecture: a survey and recent results
    Bresar, Bostjan
    Dorbec, Paul
    Goddard, Wayne
    Hartnell, Bert L.
    Henning, Michael A.
    Klavzar, Sandi
    Rall, Douglas F.
    JOURNAL OF GRAPH THEORY, 2012, 69 (01) : 46 - 76
  • [6] Some results on Vizing's conjecture and related problems
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Skrekovski, Riste
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (16-17) : 2484 - 2490
  • [7] Equality in Vizing's Conjecture Fixing One Factor of the Cartesian Product
    Khamis, S. M.
    Nazzal, Kh M.
    ARS COMBINATORIA, 2010, 96 : 375 - 384
  • [8] Chromaticity of Chordal Graphs
    Shaoji Xu
    Graphs and Combinatorics, 1997, 13 : 287 - 294
  • [9] Chromaticity of chordal graphs
    Xu, SJ
    GRAPHS AND COMBINATORICS, 1997, 13 (03) : 287 - 294
  • [10] On Adam's conjecture for circulant graphs
    Discrete Math, (497-510):
12345