On computing a minimum secure dominating set in block graphs

被引:21
作者
Pradhan, D. [1 ]
Jha, Anupriya [1 ]
机构
[1] Indian Inst Technol, Dept Appl Math, Dhanbad, Bihar, India
关键词
Domination; Secure domination; Block graphs; Linear time algorithm; NP-complete; POWER DOMINATION; TREES;
D O I
10.1007/s10878-017-0197-y
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In a graph , a set is said to be a dominating set of G if for every vertex , there exists a vertex such that . A secure dominating set of the graph G is a dominating set D of G such that for every , there exists a vertex such that and is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.
引用
收藏
页码:613 / 631
页数:19
相关论文
共 23 条
[11]   Node-searching problem on block graphs [J].
Chou, Hsin-Hung ;
Ko, Ming-Tat ;
Ho, Chin-Wen ;
Chen, Gen-Huey .
DISCRETE APPLIED MATHEMATICS, 2008, 156 (01) :55-75
[12]   Irredundance, secure domination and maximum degree in trees [J].
Cockayne, E. J. .
DISCRETE MATHEMATICS, 2007, 307 (01) :12-17
[13]  
Cockayne EJ, 2005, UTILITAS MATHEMATICA, V67, P19
[14]   Secure domination critical graphs [J].
Grobler, P. J. P. ;
Mynhardt, C. M. .
DISCRETE MATHEMATICS, 2009, 309 (19) :5820-5827
[15]  
Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
[16]  
Haynes TW., 1998, FUNDAMENTALS DOMINAT
[17]   Optimal vertex ranking of block graphs [J].
Hung, Ruo-Wei .
INFORMATION AND COMPUTATION, 2008, 206 (11) :1288-1302
[18]  
Klostermeyer W.F., 2008, DISCUSS MATH GRAPH T, V28, P267, DOI [10.7151/dmgt.1405, DOI 10.7151/DMGT.1405]
[19]  
Liu CS, 2010, P 27 WORKSH COMB MAT
[20]   On Secure Domination in Graphs [J].
Merouane, Houcine Boumediene ;
Chellali, Mustapha .
INFORMATION PROCESSING LETTERS, 2015, 115 (10) :786-790