Secure total domination in graphs: Bounds and complexity

A total dominating set of an undirected graph G = (V, E) is a set S subset of V of vertices such that each vertex of G is adjacent to at least one vertex of S. A secure total dominating set of G is a set D subset of V of vertices such that D is a total dominating set of G and each vertex v is an element of V \ D is adjacent to at least one vertex u is an element of D with the property that the set (D \ {u}) U {v} is a total dominating set of G. The secure total domination number gamma(st)(G) of G is the minimum cardinality of a secure total dominating set of G. We establish bounds on the secure total domination number. In particular, we show that every graph G with no isolated vertices satisfies gamma(st) (G) <= 2 alpha(G), where alpha(G) is the independence number of G. Further, we study the problem of finding the secure total domination number. We show that the decision version of the problem is NP-complete for chordal bipartite graphs, planar bipartite graphs with arbitrary large girth and maximum degree 3, split graphs and graphs of separability at most 2. Finally, we show that the optimisation version of the problem can be approximated in polynomial time within a factor of c In vertical bar V vertical bar for some constant c > 1 and cannot be approximated in polynomial time within a factor of c' In vertical bar V vertical bar for some constant c' < 1, unless P = NP. (C) 2017 Elsevier B.V. All rights reserved.