Domination Number of Products of Graphs

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) \geq \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) \leq 2\).