Restrained Roman Reinforcement Number in Graphs

Abstract

A restrained Roman dominating function (RRD-function) on a graph G = (V,E) is a function f from V into {0, 1, 2} satisfying: (i) every vertex u with f(u) = 0 is adjacent to a vertex v with f(v) = 2; (ii) the subgraph induced by the vertices assigned 0 under f has no isolated vertices. The weight of an RRD-function is the sum of its function value over the whole set of vertices, and the restrained Roman domination number is the minimum weight of an RRD-function on G. In this paper, we begin the study of the restrained Roman reinforcement number rrR(G) of a graph G defined as the cardinality of a smallest set of edges that we must add to the graph to decrease its restrained Roman domination number. We first show that the decision problem associated with the restrained Roman reinforcement problem is NP-hard. Then several properties as well as some sharp bounds of the restrained Roman reinforcement number are presented. In particular it is established that rrR(T) = 1 for every tree T of order at least three.