On computing a minimum secure dominating set in block graphs

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