Search

Given a positive integer t and a graph F, the goal is to assign a subset of the color set { 1 , 2 , ... , 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 RDF ) of the graph F. A t RDF is independent ( I t RDF ) if vertices assigned with non-empty sets are pairwise non-adjacent. The weight of a t RDF g of a graph F is the value w (g) = ∑ v ∈ V (F) | g (v) | . The independent t-rainbow domination number i r t (F) is the minimum weight over all I t 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. [ABSTRACT FROM AUTHOR]