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 条
  • [41] Algorithmic aspects of b-disjunctive domination in graphs
    B. S. Panda
    Arti Pandey
    S. Paul
    Journal of Combinatorial Optimization, 2018, 36 : 572 - 590
  • [42] On the algorithmic complexity of k-tuple total domination
    Lan, James K.
    Chang, Gerard Jennhwa
    DISCRETE APPLIED MATHEMATICS, 2014, 174 : 81 - 91
  • [43] Global powerful r-alliances and total k-domination in graphs
    Fernau, H.
    Rodriguez-Velazquez, J. A.
    Sigarreta, J. M.
    UTILITAS MATHEMATICA, 2015, 98 : 127 - 147
  • [44] Algorithmic aspect of stratified domination in graphs
    Chang, Gerard Jennhwa
    Chang, Chan-Wei
    Kuo, David
    Poon, Sheung-Hung
    INFORMATION PROCESSING LETTERS, 2013, 113 (22-24) : 861 - 865
  • [45] Algorithmic aspects of open neighborhood location-domination in graphs
    Panda, B. S.
    Pandey, Arti
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 290 - 306
  • [46] Algorithmic Aspects of Total Vertex-Edge Domination in Graphs
    Kumar, H. Naresh
    Chellali, Mustapha
    Venkatakrishnan, Y. B.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2023,
  • [47] Bounds on the k-domination number of a graph
    DeLaVina, Ermelinda
    Goddard, Wayne
    Henning, Michael A.
    Pepper, Ryan
    Vaughan, Emil R.
    APPLIED MATHEMATICS LETTERS, 2011, 24 (06) : 996 - 998
  • [48] On the k-domination number, the domination number and the cycle of length four
    Hansberg, Adriana
    UTILITAS MATHEMATICA, 2015, 98 : 65 - 76
  • [49] Algorithmic and complexity aspects of problems related to total Roman domination for graphs
    Abolfazl Poureidi
    Nader Jafari Rad
    Journal of Combinatorial Optimization, 2020, 39 : 747 - 763
  • [50] Algorithmic and complexity aspects of problems related to total restrained domination for graphs
    Yu Yang
    Cai-Xia Wang
    Shou-Jun Xu
    Journal of Combinatorial Optimization, 2023, 46
12345