Search

Abstract: Given a graph G and a set of t colors, assume that we assign an arbitrary subset of these colors to each vertex of G. If we require that each vertex to which an empty set is assigned has in its neighborhood all t colors, then this assignment is called a t-rainbow dominating function of the graph G. The corresponding invariant γ rt (G), which is the minimum sum of numbers of assigned colors over all vertices of G, is called the t-rainbow domination number of G. In this paper, bounds for the t-rainbow domination number of an arbitrary graph for an arbitrary positive integer t are given. The 3-rainbow domination numbers of several classes of graphs such as paths, cycles and the generalized Petersen graphs P(n, k), are investigated. The 3-rainbow domination number of P(n,1) is determined and the upper bounds for P(n,2) and P(n,3) are provided. By computer search, we obtain that the upper bounds for P(n,2) match their exact values for n ⩽17. [Copyright &y& Elsevier]