Secure total domination in chain graphs and cographs
Anupriya Jha · AKCE International Journal of Graphs and Combinatorics · 2020
Let G = (V,E) be a graph without isolated vertices. A subset D of vertices of G is called a total dominating set of G if for every u∈V, there exists a vertex v∈D such that uv∈E. A total dominating set D of a graph G is called a secure total dominating set of G if for every u∈V∖D, there exists a vertex v∈D such that uv∈E and (D∖{v})∪{u} is a total dominating set of G. The secure total domination number of G, denoted by γst(G), is the minimum cardinality of a secure total dominating set of G. Given a graph G, the secure total domination problem is to find a secure total dominating set of G with minimum cardinality. In this paper, we first show that the secure total domination problem is linear time solvable on graphs of bounded clique-width. We then propose linear time algorithms for computing the secure total domination number of chain graphs and cographs.