Semi-total Domination in Unit Disk Graphs

Let \(G=(V, E)\) be a simple undirected graph with no isolated vertex. A set \(D\subseteq V\) is a dominating set if each vertex \(u\in V\) is either in D or is adjacent to a vertex \(v\in D\) . A set \(D_{t2}\subseteq V\) is said to be a semi-total dominating set if (i) \(D_{t2}\) is a dominating set, and (ii) for every vertex \(u\in D_{t2}\) , there exists a vertex \(v\in D_{t2}\) such that the distance between u and v in G is within 2. Given a graph G, the semi-total domination problem is to find a semi-total dominating set of minimum cardinality. The semi-total domination problem is NP-complete for general graphs. It is also NP-complete on some special graph classes, such as planar, split, and chordal bipartite graphs. In this paper, we have shown that it is NP-complete for unit disk graphs. We propose a 6-factor approximation algorithm for the semi-total dominating set problem in unit disk graphs. The algorithm’s running time is O(nk), where n and k are the number of vertices and the size of the maximal independent set of the given UDG, respectively. In addition, we show that the minimum semi-total domination problem in a graph with maximum degree \(\mathbb {D}\) admits a \(2+\ln {(\mathbb {D}+1)}\) -factor approximation algorithm which is an improvement over the best-known result \(2+3\ln {(\mathbb {D}+1)}\) .