On the Roman reinforcement in graphs

A Roman dominating function (RDF) on a graph G is a function f: V (G) → {0; 1; 2} satisfying the condition that every vertex v for which f(v) = 0, is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function f is the value f(V (G)) = v∈V (G) f(v). The Roman domination number of G, denoted by R(G), is the minimum weight of an RDF on G. The Roman reinforcement number rR(G) of a graph G is the minimum number of edges that have to be added to G in order to decrease the Roman domination number. We first show that the Roman reinforcement problem is NP-complete even when restricted to bipartite graphs. Then we prove some sharp bounds on rR(G). Next we characterize trees with Roman reinforcement number greater than one. We also characterize graphs with Roman reinforcement number equal to the maximum degree