Complexity of total outer-connected domination problem in graphs

A set D⊆V is called a total dominating set of a graph G=(V,E), if for all v∈V, |NG(v)∩D|≥1. A total dominating set D of G=(V,E) is called a total outer-connected dominating set if G[V∖D] is connected. The Minimum Total Outer-connected Domination problem for a graph G=(V,E) is to find a total outer-connected dominating set of minimum cardinality. The Total Outer-connected Domination Decision problem, the decision version of the Minimum Total Outer-connected Domination problem, is known to be NP-complete for general graphs. In this paper, we strengthen this NP-completeness result by showing that the Total Outer-connected Domination Decision problem remains NP-complete for chordal graphs, split graphs, and doubly chordal graphs. We prove that the Total Outer-connected Domination Decision problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for computing the total outer-connected domination number, the cardinality of a minimum total outer-connected dominating set, of a tree. We prove that the Minimum Total Outer-connected Domination problem cannot be approximated within a factor of (1−ε)ln|V| for any ε>0, unless NP ⊆ DTIME (|V|O(loglog|V|)). Finally, we show that the Minimum Total Outer-connected Domination problem is APX-complete for bounded degree graphs.