Restrained Italian reinforcement number in graphs

AbstractA restrained Italian dominating function (RID-function) on a graph G=(V,E)is a function f:V→{0,1,2}satisfying: (i) f(N(u))≥2for every vertex u∈V(G)with f(u)=0, where N(u)is the set of vertices adjacent to u; (ii) the subgraph induced by the vertices assigned 0 under fhas no isolated vertices. The weight of an RID-function is the sum of its function value over the whole set of vertices, and the restrained Italian domination number is the minimum weight of an RID-function on G. In this paper, we initiate the study of the restrained Italian reinforcement number rrI(G)of a graph Gdefined as the cardinality of a smallest set of edges that we must add to the graph to decrease its restrained Italian domination number. We begin by showing that the decision problem associated with the restrained Italian reinforcement problem is NP-hard for arbitrary graphs. Then several properties as well as some sharp bounds of the restrained Italian reinforcement number are presented.