مشخصات پژوهش

For a graph G = (V;E), a double Roman dominating function is a function f : V (G) ! f0; 1; 2; 3g having the property that if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor with f(w)  2. The weight of a double Roman dominating function f is the value w(f) = P v2V (G) f(v). The double Roman domina- tion number of a graph G, denoted by dR(G), equals the minimum weight of a double Roman dominating function on G. The double Roman domination subdivision number sd dR(G) of a graph G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the double Roman dom- ination number. In this paper, we rst show that the decision problem associated with sd dR(G) is NP-hard and then establish upper bounds on the double Roman domination subdivision number for arbitrary graphs.