Complexity Issues of Variants of Secure Domination in Graphs

Let G=(V,E) be a simple, undirected and connected graph. A connected dominating set S⊆V(G) is a secure connected dominating set of G, if for each u∈V(G)\S, there exists v∈S such that (u,v)∈E(G) and the set (S\{v})∪{u} is a connected dominating set of G. The minimum cardinality of a secure connected dominating set of G denoted γsc(G), is called the secure connected domination number of G. In this paper, we show that the decision problems of finding a minimum secure connected dominating set and a minimum secure total dominating set are NP-complete for split graphs. We initiate the study of 2-secure domination and show that the decision problem corresponding to the computation of 2-secure domination number of a graph is NP-complete, even when restricted to split graphs or bipartite graphs. Finally we show that given two positive integers k(≥2) and n(≥max⁡{4,k}) there exists a graph G with |V(G)|=n and γsc(G)=k.