Co-secure and secure domination in graphs
Abstract
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 ν ∈ V \ S such that uν ∈ E and (S \ {u}) U {ν} 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 ∈ V\S there exists a vertex ν ∈ S such that uν ∈ E and (S \ {ν}) 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.
