Improved Total Domination and Total Roman Domination in Unit Disk Graphs

Let G= (V, E) be a simple undirected graph with no isolated vertex. A set Dₜ V is a total dominating set of G if (i) Dₜ is a dominating set, and (ii) the set Dₜ induces a subgraph with no isolated vertex. The total dominating set of minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total domination number (ₜ (G) ). Given a graph G, the total dominating set (TDS) problem is to find a total dominating set of minimum cardinality. A Roman dominating function (RDF) on a 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 RDF f of a graph G is said to be a total Roman dominating function (TRDF) if the induced subgraph of V₁ V₂ does not contain any isolated vertex, where Vᵢ=\u V|f (u) =i\. Given a graph G, the total Roman dominating set (TRDS) problem is to minimize the weight, W (f) =ₔ ₕ f (u), called the total Roman domination number (ₓₑ (G) ). In this paper, we are the first to show that the TRDS problem is NP-complete in unit disk graphs (UDGs). Furthermore, we propose a 7. 17- factor approximation algorithm for the TDS problem and a 6. 03- factor approximation algorithm for the TRDS problem in geometric unit disk graphs. The running time for both algorithms is notably bounded by O (nk), where n represents the number of vertices in the given UDG and k represents the size of the independent set in (i. e. , D and V₂ in TDS and TRDS problems, respectively) the given UDG.