Complexity of Roman {2}-domination and the double Roman domination in graphs
Padamutham Chakradhar, Venkata Subba Reddy Palagiri · AKCE International Journal of Graphs and Combinatorics · 2020
For a simple, undirected graph G=(V,E), a Roman {2}-dominating function (R2DF) f:V→{0,1,2} has the property that for every vertex v∈V with f(v) = 0, either there exists a vertex u∈N(v), with f(u) = 2, or at least two vertices x,y∈N(v) with f(x)=f(y)=1. The weight of an R2DF is the sum f(V)=∑v∈Vf(v). The minimum weight of an R2DF is called the Roman {2}-domination number and is denoted by γ{R2}(G). A double Roman dominating function (DRDF) on G is a function f:V→{0,1,2,3} such that for every vertex v∈V if f(v) = 0, then v has at least two neighbors x,y∈N(v) with f(x)=f(y)=2 or one neighbor w with f(w) = 3, and if f(v) = 1, then v must have at least one neighbor w with f(w)≥2. The weight of a DRDF is the value f(V)=∑v∈Vf(v). The minimum weight of a DRDF is called the double Roman domination number and is denoted by γdR(G). Given an graph G and a positive integer k, the R2DP (DRDP) problem is to check whether G has an R2DF (DRDF) of weight at most k. In this article, we first show that the R2DP problem is NP-complete for star convex bipartite graphs, comb convex bipartite graphs and bisplit graphs. We also show that the DRDP problem is NP-complete for star convex bipartite graphs and comb convex bipartite graphs. Next, we show that γ{R2}(G), and γdR(G) are obtained in linear time for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. Finally, we propose a 2(1+ ln (Δ+1))-approximation algorithm for the minimum Roman {2}-domination problem and 3(1+ ln (Δ+1))-approximation algorithm for the minimum double Roman domination problem, where Δ is the maximum degree of G.