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