مشخصات پژوهش

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 w with f(w) ¼ 3, and if f(v) ¼ 1, then vertex v must have at least one neighbor w with fðwÞ 2: The weight of a double Roman dominating function f is the value xðfÞ ¼ Rv2VðGÞfðvÞ: The double Roman domination number of a graph G, denoted by cdRðGÞ, equals the minimum weight of a double Roman dominating function on G. The double Roman reinforcement number rdRðGÞ of a graph G is the minimum number of edges that have to be added to G in order to decrease the double Roman domination number. In this paper, we first show that the decision problem associated to the double Roman reinforcement problem is NPhard even when restricted to bipartite graphs and then we investigate the properties of double Roman reinforcement number in graphs, and we present some sharp bounds for rdRðGÞ: Next we characterize trees with double Roman reinforcement number greater than one.