مشخصات پژوهش

Let k be a positive integer. A restrained k-rainbow dominating function (RkRD-function) of a graph G = (V,E) is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} satisfying: (i) for any vertex v ∈ V with f(v) = ∅ the condition u∈N(v) f(u) = {1, 2, . . . , k} is fulfilled, where N(v) is the set of all vertices adjacent to v; (ii) the subgraph induced by the vertices assigned ∅ under f has no isolated vertices. The weight of an RkRD-function f is the value ω(f) = v∈V |f(v)|, and the restrained k-rainbow domination number of G, denoted by γrrk(G), is the minimum weight of an RkRD-function of G. In this paper, we continue the study of the restrained k-rainbow reinforcement number rrrk(G) of a graph G defined as the cardinality of a smallest set of edges that we must add to G to decrease γrrk(G). We shall first show that the decision problem associated with γrrk(G) is NP-hard for arbitrary graphs. Then several properties as well as some sharp bounds of the restrained k-rainbow reinforcement number are investigated.