Algorithmic Complexity of Secure Connected Domination in Graphs

Abstract

Let $G=(V,E)$ be a simple, undirected and connected graph. A connected (total) dominating set $S\subseteq V$ is a secure connected (total) dominating set of $G$, if for each $u\in V\setminus S$, there exists $v\in S$ such that $uv\in E$ and $(S\setminus \{v\})\cup \{u\}$ is a connected (total) dominating set of $G$. The minimum cardinality of a secure connected (total) dominating set of $G$ denoted by ${\gamma }_{sc}(G)({\gamma }_{st}(G))$, is called the secure connected (total) domination number of $G$. In this paper, we show that the decision problems corresponding to secure connected domination number and secure total domination number are NP-complete even when restricted to split graphs or bipartite graphs. The NP-complete reductions also show that these problems are w[2]-hard. We also prove that the secure connected domination problem is linear time solvable in block graphs and threshold graphs.