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 条
  • [41] A linear-time algorithm for semitotal domination in strongly chordal graphs
    Tripathi, Vikash
    Pandey, Arti
    Maheshwari, Anil
    DISCRETE APPLIED MATHEMATICS, 2023, 338 : 77 - 88
  • [42] On incidence coloring conjecture in Cartesian products of graphs
    Gregor, Petr
    Luzar, Borut
    Sotak, Roman
    DISCRETE APPLIED MATHEMATICS, 2016, 213 : 93 - 100
  • [43] A proof of the upper matching conjecture for large graphs
    Davies, Ewan
    Jenssen, Matthew
    Perkins, Will
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2021, 151 : 393 - 416
  • [44] Jones’ conjecture for Halin graphs and a bit more
    Eötvös Loránd University, Budapest, Hungary
    不详
    arXiv,
  • [45] Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
    Papadopoulos, Charis
    Tzimas, Spyridon
    COMBINATORIAL ALGORITHMS (IWOCA 2022), 2022, 13270 : 466 - 479
  • [46] Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
    Papadopoulos, Charis
    Tzimas, Spyridon
    ALGORITHMICA, 2024, 86 (03) : 874 - 906
  • [47] Computing a minimum outer-connected dominating set for the class of chordal graphs
    Keil, J. Mark
    Pradhan, D.
    INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) : 552 - 561
  • [48] Towards the Conjecture on Domination Versus Edge Domination in Graphs
    Maniya, Paras
    Pradhan, Dinabandhu
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2024, 47 (01)
  • [49] 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
  • [50] Towards the Conjecture on Domination Versus Edge Domination in Graphs
    Paras Maniya
    Dinabandhu Pradhan
    Bulletin of the Malaysian Mathematical Sciences Society, 2024, 47
12345