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).

Let G = (V, E) be a simple, undirected and connected graph. A Roman dominating function (RDF) on the graph G is a function f : V → {0, 1, 2} such that each vertex v ∈ V with f(v) = 0 is adjacent to at least one vertex u ∈ V with f(u) = 2. A total Roman dominating function (TRDF) of G is a function f : V → {0, 1, 2} such that (i) it is a Roman dominating function, and (ii) the vertices with non-zero weights induce a subgraph with no isolated vertex. The total Roman dominating set (TRDS) problem is to minimize the associated weight, (Formula presented), called the total Roman domination number (γtR(G)). Similarly, a subset S ⊆ V is said to be a total dominating set (TDS) on the graph G if (i) S is a dominating set of G, and (ii) the induced subgraph G[S] does not have any isolated vertex. The objective of the TDS problem is to minimize the cardinality of the TDS of a given graph. The TDS problem is NP-complete for general graphs. In this paper, we propose a simple 10.5 -factor approximation algorithm for TRDS problem in UDGs. The running time of the proposed algorithm is O(|V |log k), where k is the number of vertices with weights 2. It is an improvement over the best-known 12-factor approximation algorithm with running time O(|V |log k) available in the literature. Next, we propose another algorithm for the TDS problem in UDGs, which improves the previously best-known approximation factor from 8 to 7.79. The running time of the proposed algorithm is O(|V | + |E|).

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 said to be a semi-total dominating set if (i) Dt2 is a dominating set, and (ii) for every vertex u∈ Dt2, there exists a vertex v∈ Dt2 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 D admits a 2 + ln (D+ 1 ) -factor approximation algorithm which is an improvement over the best-known result 2 + 3 ln (D+ 1 ).