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