Secure total domination in chain graphs and cographs

Abstract

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 there exists a vertex such that A total dominating set D of a graph G is called a secure total dominating set of G if for every there exists a vertex such that and is a total dominating set of G. The secure total domination number of G, denoted by 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.

Keywords

• total domination
• secure total domination
• chain graphs
• cographs
• linear time algorithm