Dominating direct products of graphs

被引：22

作者：

Bresar, Bostjan ^{[1
]}

Klavzar, Sandi ^{[2
]}

Rall, Douglas F. ^{[3
]}

机构：

[1] Univ Maribor, FEECS, Maribor 2000, Slovenia

[2] Univ Maribor, Dept Math & Comp Sci, Maribor 2000, Slovenia

[3] Furman Univ, Dept Math, Greenville, SC USA

来源：

DISCRETE MATHEMATICS | 2007年 / 307卷 / 13期

关键词：

domination; paired-domination; upper domination; direct product;

D O I：

10.1016/j.disc.2006.09.013

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, gamma(G x H) <= 3 gamma(G)gamma(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Gamma(G x H) >= Gamma(G)Gamma(H), thus confirming a conjecture from [R. Nowakowski, D. F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that gamma(pr)(G x H) <= gamma(pr)(G) <= gamma(pr)(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound. (C) 2006 Elsevier B.V. All rights reserved.

引用

页码：1636 / 1642

页数：7

共 20 条

[1]

Abay-Asmerom G, 2005, ARS COMBINATORIA, V74, P201

[2]

BRESAR B, 2005, ELECTRON J COMB, V12, P101

[3] Domination number of the cross product of paths [J].

Chérifi, R ;

Gravier, S ;

Lagraula, X ;

Payan, C ;

Zighem, I .

DISCRETE APPLIED MATHEMATICS, 1999, 94 (1-3) :101-139

[4]

Dorbec P., 2006, Discussiones Mathematicae Graph Theory, V26, P103, DOI 10.7151/dmgt.1305

[5]

ELZAHAR M, 2004, CAHIERS LAB LEIBNIZ, V97

[6] ON THE DOMINATION NUMBER OF CROSS PRODUCTS OF GRAPHS [J].

GRAVIER, S ;

KHELLADI, A .

DISCRETE MATHEMATICS, 1995, 145 (1-3) :273-277

[7]

Haynes T. W., 1998, FUNDAMENTALS DOMINAT

[8]

Haynes TW, 1998, NETWORKS, V32, P199, DOI 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO

[9]

2-F

[10] Smallest independent dominating sets in Kronecker products of cycles [J].

Jha, PK .

DISCRETE APPLIED MATHEMATICS, 2001, 113 (2-3) :303-306

← 1 2 →