Domination Number of Products of Graphs

Abstract

Let $G=(X,E)$ be any graph. Then $D\subset X$ is called a dominating set of $G$ if for every vertex $x\in X–D$, $x$ is adjacent to at least one vertex of $D$. The domination number, $\gamma (G)$, is $min\{|D|\mid D$ { is a dominating set of } $G\}$. In 1965 Vizing gave the following conjecture: For any two graphs $G$ and $H$

$$\gamma (G\times H)\ge \gamma (G).\gamma (H).$$

In this paper, it is proved that $\gamma (G\times H)>\gamma (G).\gamma (H)$ if $H$ is either one of the following graphs: (a) $H=G^{-}$, i.e., complementary graph of $G$, (b) $H=C_m$, i.e., a cycle of length $m$ or (c) $\gamma (H)\le 2$.