Co-secure and secure domination in graphs

A set S ⊆ V is a co-secure dominating set (CSDS) of a graph G = (V, E) if S is a dominating set, and for each u ∈ S there exists a vertex ∈ VS such that uv ∈ E and (S{u}) U {v} is a dominating set. The minimum cardinality of a co-secure dominating set in G is the co-secure domination number γcs(G) of G. In this paper we initiate a study of this parameter. We determine the co-secure domination number of some families of standard graphs and obtain sharp bounds. We also prove that the decision problem for this parameter is NP-complete even when restricted to bipartite, chordal or planar graphs. A set S ⊆ V is a secure dominating set of a graph G = (V, E) if for each u ∈ VS there exists a vertex v ∈ S such that uv ∈ E and (S{v})U {u} is a dominating set. The minimum cardinality of a secure dominating set in G is the secure domination number γs(G) of G. We present a few basic results on this parameter