Dominating Cartesian products of cycles Original Research Article

Let γ(G) be the domination number of a graph G and let G □ H denote the Cartesian product of graphs G and H. We prove that γ(X) = (Πmk = 1nk)(2m + 1), where X = C1□C2□ … □ Cm and all nk = ¦Ck¦, 1 ⩽ k ⩽ 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 to C3, C4 or C5, respectively.