Search

In a graph G=(V,E), a set D⊆V is said to be a dominating set of G if for every vertex u∈V\D, there exists a vertex v∈D such that uv∈E. A secure dominating set of the graph G is a dominating set D of G such that for every u∈V\D, there exists a vertex v∈D such that uv∈E and (D\{v})∪{u} 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. [ABSTRACT FROM AUTHOR]