Secure total domination in graphs: properties and complexity

Abstract

A vertex subset S of an undirected graph G = (V, E) is a total dominating set of G if each vertex of G is adjacent to at least one vertex of S. In this paper, we consider secure total dominating sets, i.e., total dominating sets D of G satisfying the following condition: each vertex vV D is adjacent to at least one vertex uD with the property that the set Duv is total dominating in G. The minimum size of a secure total dominating set of G is the secure total domination number of G. We present a characterization of secure total dominating sets in (P5, bull)-free graphs and new bounds on the secure total domination number. Besides, we consider a problem of finding this number and provide results on the complexity of this problem in special graph classes.