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 条
12345