Independent Rainbow Domination of Graphs

Given a positive integer t and a graph F, the goal is to assign a subset of the color set \(\{1,2,\ldots ,t\}\) to every vertex of F such that every vertex with the empty set assigned has all t colors in its neighborhood. Such an assignment is called the t-rainbow dominating function (\(t\mathrm{RDF}\)) of the graph F. A \(t\mathrm{RDF}\) is independent (\(It\mathrm{RDF}\)) if vertices assigned with non-empty sets are pairwise non-adjacent. The weight of a \(t\mathrm{RDF}\) g of a graph F is the value \(w(g) =\sum _{v \in V(F)}|g(v)|\). The independent t-rainbow domination number \(i_{rt}(F)\) is the minimum weight over all \(It\mathrm{RDF}\)s of F. In this article, it is proved that the independent t-rainbow domination problem is NP-complete even if the input graph is restricted to a bipartite graph or a planar graph, and the results of the study provide some bounds for the independent t-rainbow domination number of any graph for a positive integer t. Moreover, the exact values and bounds of the independent t-rainbow domination numbers of some Petersen graphs and torus graphs are given.