DOMINATING CARTESIAN PRODUCTS OF CYCLES

Let gamma(G) be the domination number of a graph G and let G square H denote the Cartesian product of graphs G and H. We prove that gamma(X) = (Pi(k=1)(m), n(k))/(2m + 1), where X = C-1 square C-2 square ... sq uare C-m and all n(k) = \C-k\, 1 less than or equal to k less than or equal to m, are multiples of 2m + 1. The methods we use to prove this result immediately lead to an algorithm for finding minimum dominating sets of the considered graphs. Furthermore the domination numbers of products of two cycles are determined exactly if one factor is equal t o C-3, C-4 or C-5, respectively.