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 条
  • [31] TOMESCU'S GRAPH COLORING CONJECTURE FOR l-CONNECTED GRAPHS
    Engbers, John
    Erey, Aysel
    Fox, Jacob
    He, Xiaoyu
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) : 1478 - 1502
  • [32] Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
    Kwan, Matthew
    Sah, Ashwin
    Sauermann, Lisa
    Sawhney, Mehtaab
    FORUM OF MATHEMATICS PI, 2023, 11
  • [33] Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs
    Chu, Kuan-Ting
    Lin, Wu-Hsiung
    Chen, Chiuyuan
    DISCRETE APPLIED MATHEMATICS, 2019, 259 : 41 - 52
  • [34] On a conjecture of TxGraffiti: Relating zero forcing and vertex covers in graphs
    Brimkov, Boris
    Davila, Randy
    Schuerger, Houston
    Young, Michael
    DISCRETE APPLIED MATHEMATICS, 2024, 359 : 290 - 302
  • [35] A Width Parameter Useful for Chordal and Co-comparability Graphs
    Kang, Dong Yeap
    Kwon, O-Joung
    Stromme, Torstein J. F.
    Telle, Jan Arne
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 2017, 10167 : 93 - 105
  • [36] Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs
    Bousquet, Nicolas
    Thomasse, Stephan
    COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (04) : 512 - 514
  • [37] Chromatic numbers, Sabidussi's Theorem and Hedetniemi's conjecture for non-commutative graphs
    Kim, Se-Jin
    Mehta, Arthur
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 582 : 291 - 309
  • [38] Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
    Chang, MS
    Chen, YH
    Chang, GJ
    Yan, JH
    DISCRETE APPLIED MATHEMATICS, 1996, 66 (03) : 189 - 203
  • [39] The k-path vertex cover: General bounds and chordal graphs
    Bujtas, Csilla
    Jakovac, Marko
    Tuza, Zsolt
    NETWORKS, 2022, 80 (01) : 63 - 76
  • [40] COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS
    Pradhan, D.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (03)
12345