Domination number of the cross product of paths

被引：14
作者：
Chérifi, R
Gravier, S
Lagraula, X
Payan, C
Zighem, I
机构：
[1] Univ Grenoble 1, IMAG, LSD2, F-38041 Grenoble 9, France
[2] CNRS, Lab Leibniz, IMAG, F-38031 Grenoble, France
来源：
DISCRETE APPLIED MATHEMATICS | 1999年 / 94卷 / 1-3期
关键词：
D O I：
10.1016/S0166-218X(99)00016-5
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The problem of determining the domination number of an arbitrary grid graph is known to be NP-complete, but the complexity of the same problem on complete grid graphs is still unknown. In the present paper we study the same problem on a similar grid graph defined by the cross product of two paths P-k and P-n. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：101 / 139
页数：39
相关论文
共 11 条
  • [1] [Anonymous], 1986, C NUMER
  • [2] CHANG TY, 1994, ARS COMBINATORIA, V38, P97
  • [3] THE DOMINATION NUMBERS OF THE 5XN AND 6XN GRID GRAPHS
    CHANG, TY
    CLARK, WE
    [J]. JOURNAL OF GRAPH THEORY, 1993, 17 (01) : 81 - 107
  • [4] UNIT DISK GRAPHS
    CLARK, BN
    COLBOURN, CJ
    JOHNSON, DS
    [J]. DISCRETE MATHEMATICS, 1990, 86 (1-3) : 165 - 177
  • [5] ON THE DOMINATION NUMBER OF CROSS PRODUCTS OF GRAPHS
    GRAVIER, S
    KHELLADI, A
    [J]. DISCRETE MATHEMATICS, 1995, 145 (1-3) : 273 - 277
  • [6] HARE EO, 1995, GRAPH THEORY COMBINA, P497
  • [7] Jacobson M. S., 1984, I. Ars Combin., V18, P33
  • [8] THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE
    JOHNSON, DS
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1985, 6 (03): : 434 - 451
  • [9] DOMINATING CARTESIAN PRODUCTS OF CYCLES
    KLAVZAR, S
    SEIFTER, N
    [J]. DISCRETE APPLIED MATHEMATICS, 1995, 59 (02) : 129 - 136
  • [10] On a Vizing-like conjecture for direct product graphs
    Klavzar, S
    Zmazek, B
    [J]. DISCRETE MATHEMATICS, 1996, 156 (1-3) : 243 - 246
12