On Secure Domination in Graphs

A set $D\subset V$ of a graph $G=(V,E)$ is a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. A secure dominating set S of a graph G is a dominating set with the property that each vertex $u\in V\backslash S$ is adjacent to a vertex $v\in S$ such that $(S\backslash \{v\})\cup \{u\}$ is a dominating set. The secure domination number ${\gamma }_s(G)$ equals the minimum cardinality of a secure dominating set of G. We first show that the problem of computing the secure domination number is NP‐complete for bipartite and split graphs. Then we present bounds relating the secure domination number to the domination number $\gamma (G)$ , the independence number ${\beta }_0(G)$ and the independent domination number $i(G)$ . In particular, we prove that ${\gamma }_s(G)\le \gamma (G)+{\beta }_0(G)‐1$ if G is an arbitrary graph, ${\gamma }_s(G)\le \frac{3}{2}{\beta }_0(G)$ if G is triangle‐free, and ${\gamma }_s(G)\le {\beta }_0(G)$ if G has girth at least six. Finally, we show for the class of trees T that ${\gamma }_s(T)\ge i(T)$ and ${\gamma }_s(T)>{\beta }_0(T)/2$ . The last result answers the question posed by Mynhardt at the 22nd Clemson mini‐Conference, 2007