Algorithmic aspects of the k-domination problem in graphs

被引：18

作者：

Lan, James K. ^{[1
]}

Chang, Gerard Jennhwa ^{[1
,2
,3
]}

机构：

[1] Natl Taiwan Univ, Dept Math, Taipei 10617, Taiwan

[2] Natl Taiwan Univ, Taida Inst Math Sci, Taipei 10617, Taiwan

[3] Natl Ctr Theoret Sci, Taipei Off, Taipei, Taiwan

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 10-11期

关键词：

k-domination; Tree; Block graph; Cactus; Block-cactus graph; Split graph; Algorithm; NP-complete; NUMBER;

D O I：

10.1016/j.dam.2013.01.015

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For a positive integer k, a k-dominating set of a graph G is a subset D subset of V (G) such that every vertex not in D is adjacent to at least k vertices in D. The k-domination problem is to determine a minimum k-dominating set of G. This paper studies the k-domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the k-domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs includes trees, block graphs, cacti and block-cactus graphs. We also establish NP-completeness of the k-domination problem in split graphs. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：1513 / 1520

页数：8

共 50 条

[1] Algorithmic Results of Independent k-Domination on Weighted Graphs
Yen, William C-K.
CHIANG MAI JOURNAL OF SCIENCE, 2011, 38 : 58 - 70
[2] Independence and k-domination in graphs
Hansberg, Adriana
Meierling, Dirk
Volkmann, Lutz
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (05) : 905 - 915
[3] ON THE TOTAL k-DOMINATION IN GRAPHS
Bermudo, Sergio
Hernandez-Gomez, Juan C.
Sigarreta, Jose M.
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2018, 38 (01) : 301 - 317
[4] ROMAN k-DOMINATION IN GRAPHS
Kaemmerling, Karsten
Volkmann, Lutz
JOURNAL OF THE KOREAN MATHEMATICAL SOCIETY, 2009, 46 (06) : 1309 - 1318
[5] Improved Algorithms for k-Domination and Total k-Domination in Proper Interval Graphs
Chiarelli, Nina
Hartinger, Tatiana Romina
Alejandra Leoni, Valeria
Lopez Pujato, Maria Ines
Milanic, Martin
COMBINATORIAL OPTIMIZATION, ISCO 2018, 2018, 10856 : 290 - 302
[6] On k-domination and j-independence in graphs
Hansberg, Adriana
Pepper, Ryan
DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) : 1472 - 1480
[7] Efficient Algorithms to Solve k-Domination Problem on Permutation Graphs
Rana, Akul
Pal, Anita
Pal, Madhumangal
HIGH PERFORMANCE NETWORKING, COMPUTING, AND COMMUNICATION SYSTEMS, 2011, 163 : 327 - +
[8] Total k-domination in Cartesian product graphs
Bermudo, S.
Sanchez, J. L.
Sigarreta, J. M.
PERIODICA MATHEMATICA HUNGARICA, 2017, 75 (02) : 255 - 267
[9] Hardness results of global total k-domination problem in graphs
Panda, B. S.
Goyal, Pooja
DISCRETE APPLIED MATHEMATICS, 2022, 319 : 223 - 238
[10] Total k-domination in strong product graphs
Bermudo, S.
Hernandez-Gomez, J. C.
Sigarreta, J. M.
DISCRETE APPLIED MATHEMATICS, 2019, 263 : 51 - 58

← 1 2 3 4 5 →