On the domination number of the cartesian product of the cycle of length n and any graph

Abstract

Let γ (G) denote the domination number of a graph G and let C n □ G denote the cartesian product of C n , the cycle of length n ≥ 3, and G. In this paper, we are mainly concerned with the question: which connected nontrivial graphs satisfy γ (C n □ G) = γ (C n ) γ (G)? We prove that this equality can only hold if n ≡ 1 (mod 3). In addition, we characterize graphs which satisfy this equality when n = 4 and provide infinite classes of graphs for general n ≡ 1 (mod 3). © 2006 Elsevier B.V. All rights reserved.