double roman domination in graphs: algorithmic complexity

Let g = (v, e) be a graph. a double roman dominating function (drdf) of g is a function f : v → {0, 1, 2, 3} such that, for each v ∈ v with f(v) = 0, there is a vertex u adjacent to v with f(u) = 3 or there are vertices x and y adjacent to v such that f(x) = f(y) = 2 and for each v ∈ v with f(v) = 1, there is a vertex u adjacent to v with f(u) > 1. the weight of a drdf f is f(v ) = ∑ v∈v f(v). let n and k be integers such that 3 ≤ 2k + 1 ≤ n. the generalized petersen graph gp(n, k) = (v, e) is the graph with v = {u1, u2, . . . , un} ∪ {v1, v2, . . . , vn} and e = {uiui+1, uivi, vivi+k : 1 ≤ i ≤ n}, where addition is taken modulo n. in this paper, we firstly prove that the decision problem associated with double roman domination is np-complete even restricted to planar bipartite graphs with maximum degree at most 4. next, we give a dynamic programming algorithm for computing a minimum drdf (i.e., a drdf with minimum weight along all drdfs) of gp(n, k) in o(n81k) time and space and so a minimum drdf of gp(n, o(1)) can be computed in o(n) time and space.