On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G   coincides with the ordinary domination of the prism G□K2G□K2. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k)GP(n,k) this number is between ⌈4n/5⌉⌈4n/5⌉ and n with both bounds being sharp.