Restrained Italian reinforcement number in graphs

Abstract

AbstractA restrained Italian dominating function (RID-function) on a graph [Formula: see text] is a function [Formula: see text] satisfying: (i) [Formula: see text] for every vertex [Formula: see text] with [Formula: see text], where [Formula: see text] is the set of vertices adjacent to u; (ii) the subgraph induced by the vertices assigned 0 under f has 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 [Formula: see text] 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 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.

Keywords

• Restrained Italian domination
• restrained Italian reinforcement
• NP-hardness