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

共 14 条

[1]

Aharoni R, 2000, J GRAPH THEOR, V35, P83, DOI 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO

[2]

2-V

[3] A tree version of Konig's theorem [J].

Aharoni, R ;

Berger, E ;

Ziv, R .

COMBINATORICA, 2002, 22 (03) :335-343

[4]

Barcalkin A., 1979, B AKAD STIINTE RSS M, V1, P5

[5]

Clark W. E., 2000, ELECTRON J COMB, V7

[6]

Clark WE, 2003, ARS COMBINATORIA, V69, P97

[7]

Hartnell B, 1998, MG TXB PUR APPL MATH, V209, P163

[8]

Hartnell B.L., 1991, C NUMER, V82, P87

[9]

Imrich W, 2000, WIL INT S D

[10] KNESER CONJECTURE, CHROMATIC NUMBER, AND HOMOTOPY [J].

LOVASZ, L .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 25 (03) :319-324

← 1 2 →