THE DOMINATION NUMBER OF GRIDS

被引：71

作者：

Goncalves, Daniel ^{[1
]}

Pinlou, Alexandre ^{[1
,2
]}

Rao, Michael ^{[3
,4
]}

Thomasse, Stephan ^{[1
]}

机构：

[1] Univ Montpellier, CNRS, LIRMM, F-34095 Montpellier, France

[2] Univ Montpellier 3, Dept Math & Informat Appl, F-34199 Montpellier 5, France

[3] Univ Bordeaux, CNRS, LABRI, F-33405 Talence, France

[4] CNRS, Lab JV Poncelet, Moscow, Russia

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2011年 / 25卷 / 03期

关键词：

graph; domination; grid;

D O I：

10.1137/11082574

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we conclude the calculation of the domination number of all (n, m) grid graphs. Indeed, we prove Chang's conjecture saying that for every 16 <= n <= m, gamma((Gn, m)) = [(n+2)(m+2)/5] - 4.

引用

页码：1443 / 1453

页数：11

共 10 条

[1]

[Anonymous], 1986, C NUMER

[2] All-pairs shortest paths with real weights in O(n3/logn) time [J].

Chan, Timothy M. .

ALGORITHMICA, 2008, 50 (02) :236-243

[3]

Chang T.Y., 1992, PhD thesis

[4]

CHANG TY, 1994, ARS COMBINATORIA, V38, P97

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

CHANG, TY ;

CLARK, WE .

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

[6]

Cockayne E.J., 1985, CONGR NUMER CONF J N, V47, P217

[7]

FISHER DC, 1993, DOMINATION NUM UNPUB

[8]

Guichard D. R., 2004, Journal of Combinatorial Mathematics and Combinatorial Computing, V49, P215

[9]

Jacobson M. S., 1984, Ars Comb., V18, P33

[10]

SINGH HG, 1987, C NUMER, V59, P297

← 1 →