Secure total domination in chain graphs and cographs

AKCE International Journal of Graphs and Combinatorics

Anupriya Jha¹ 

[1] Indian Institute of Technology (ISM);

关键词: total domination;    secure total domination;    chain graphs;    cographs;    linear time algorithm;   

DOI  :  10.1016/j.akcej.2019.10.005

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown