On a Vizing-like conjecture for direct product graphs (Q1923517)

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating, if for each \(x \in V(G) - D\) there exists \(y \in D\) adjacent to \(x\). The minimum number of vertices of a dominating set of \(G\) is called the domination number \(\gamma (G)\) of \(G\). A direct product \(G \times H\) of graphs \(G\) and \(H\) is the graph whose vertex set is \(V(G) \times V(H)\) and in which two vertices \((a,x)\) and \((b,y)\) are adjacent if and only if \(a\), \(b\) are adjacent in \(G\) and \(x\), \(y\) are adjacent in \(H\). The authors prove that for each \(k \geq 0\) there exists a graph \(G\) such that \(\gamma (G \times G) \leq \gamma (G)^2 - k\). This disproves a conjecture of \textit{S. Gravier} and \textit{A. Khelladi} [Discrete Math. 145, No. 1-3, 273-277 (1995; Zbl 0833.05053)] that always \(\gamma (G \times H) \geq \gamma (G) \cdot \gamma (H)\). A similar conjecture for another type of product of graphs was suggested by V. G. Vizing.