|
Abstract
|
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.
|