Abstract
Let G=(V,E) be a simple undirected graph with no isolated vertex. A set D⊆V is a dominating set if each vertex u∈V is either in D or is adjacent to a vertex v∈D. A set Dt2⊆V is called a semi-total dominating set if (i)Dt2 is a dominating set, and (ii) for every vertex u∈Dt2, there exists another vertex v∈Dt2 such that the distance between u and v in G is at most 2. Given a graph G, the semi-total domination problem finds a semi-total dominating set of minimum size. This problem is known to be NP-complete for general graphs and remains NP-complete for some special graph classes, such as planar, split, and chordal bipartite graphs. In this paper, we demonstrate that the problem is also NP-complete for unit disk graphs and propose a 6-factor approximation algorithm. The algorithm’s running time is O(nlogn), where n is the number of vertices in the given unit disk graph. In addition, we show that the minimum semi-total domination problem in a graph with maximum degree Δ admits a 2+ln(Δ+1)-factor approximation algorithm, which is an improvement over the best-known result 2+3ln(Δ+1).