Rainbow Domination in Cartesian Product of Paths and Cycles.

Let G = (V , E) be a graph and k be an integer representing k colors. There is a function f from V to the power set of k colors satisfying every vertex v ∈ V assigned ∅ under f in its neighborhood has all the colors, then f is called a k -rainbow dominating function (k RDF) on G. The weight of f is the sum of the number of colors on each vertex all over the graph. The k -rainbow domination number of G is the minimum weight of k RDFs on G , denoted by γ r k (G). The aim of this paper is to investigate the k -rainbow (k = 3 , 4) domination number of the Cartesian product of paths P m □ P n and the Cartesian product of paths and cycles P m □ C n . For P m □ P n , we determine the value γ r 3 (P 4 □ P n) = 2 n + 2 and present γ r 3 (P m □ P n) ≤ m n 2 + 2 for m ≥ 5. For P m □ C n , we determine the values of γ r 3 (P m □ C n) for m = 3 , 4 or n = 3 , 4 and γ r 4 (P m □ C n) for m = 3 or n = 3. [ABSTRACT FROM AUTHOR]