Article ID Journal Published Year Pages File Type
421436 Discrete Applied Mathematics 2007 8 Pages PDF
Abstract

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

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,