On computing a minimum secure dominating set in block graphs

In a graph (G=(V,E)), a set (D subseteq V) is said to be a dominating set of G if for every vertex (uin V{setminus }D), there exists a vertex (vin D) such that (uvin E). A secure dominating set of the graph G is a dominating set D of G such that for every (uin V{setminus }D), there exists a vertex (vin D) such that (uvin E) and ((D{setminus }{v})cup {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.