Total domination number of grid graphs

被引：46

作者：

Gravier, S ^{[1
]}

机构：

[1] CNRS, Lab Leibniz, IMAG, F-38031 Grenoble 1, France

来源：

DISCRETE APPLIED MATHEMATICS | 2002年 / 121卷 / 1-3期

关键词：

domination parameters; Lee-codes; graph products;

D O I：

10.1016/S0166-218X(01)00297-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We use the link between the existence of tilings in Manhattan metric with {1}-bowls and minimum total dominating sets of Cartesian products of paths and cycles, From the existence of such a tiling, we deduce the asymptotical values of the total domination numbers of these graphs and we deduce the total domination numbers of some Cartesian products of cycles. Finally, we investigate the problem of total domination numbers for some Cartesian products of two paths. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：119 / 128

页数：10

共 13 条

[1]

[Anonymous], DOMINATION NUMBER CO

[2]

Chang T. Y., 1992, THESIS U S FLORIDA

[3] THE DOMINATION NUMBERS OF THE 5XN AND 6XN GRID GRAPHS [J].

CHANG, TY ;

CLARK, WE .

JOURNAL OF GRAPH THEORY, 1993, 17 (01) :81-107

[4]

COCKAYNE EJ, 1985, C NUMER, V47, P217

[5]

Golomb S. W., 1968, Error correcting codes, P175

[6] Variations on tilings in the Manhattan metric [J].

Gravier, S ;

Mollard, M ;

Payan, C .

GEOMETRIAE DEDICATA, 1999, 76 (03) :265-273

[7] On domination numbers of Cartesian product of paths [J].

Gravier, S ;

Mollard, M .

DISCRETE APPLIED MATHEMATICS, 1997, 80 (2-3) :247-250

[8]

Jacobson M. S., 1984, I. Ars Combin., V18, P33

[9] THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].

JOHNSON, DS .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1985, 6 (03) :434-451

[10] DOMINATING CARTESIAN PRODUCTS OF CYCLES [J].

KLAVZAR, S ;

SEIFTER, N .

DISCRETE APPLIED MATHEMATICS, 1995, 59 (02) :129-136

← 1 2 →