Tightness of domination inequalities for direct product graphs (Q2037578): Difference between revisions

Let \(G = (V (G), E(G))\) and \(H = (V (H), E(H))\) be graphs with no isolated vertices. The direct product (or tensor product) of \(G\) and \(H\), denoted by \(G \times H\), is the graph on \(V (G) \times V (H)\) where vertices \((u_G, u_H)\) and \((v_G , v_H)\) are adjacent if and only if \(\{u_G, v_G\} \in E(G)\) and \(\{u_H , v_H\} \in E(H)\). The Cartesian product of two graphs \(G\) and \(H\), denoted by \(G \square H\), is the graph on vertex set \(V (G) \times V (H)\) with vertex \((u_G, u_H)\) adjacent to \((v_G , v_H)\) if and only if either \(u_G = v_G\) and \(\{u_H , v_H\}\in E(H)\), or \(\{u_G, v_G\}\in E(G)\) and \(u_H = v_H\).\\ The domination number \(\gamma (G)\) is the minimum size of a dominating set in \(G\). The paired domination number \(\gamma_{pr} (G)\) of \(G\) is the minimum size of a dominating set whose induced subgraph admits a perfect matching. The upper domination number \(\Gamma(G)\) of \(G\) is the maximum size of a minimal dominating set in \(G\). In this paper, there are three main results as follows. \begin{itemize} \item[1.] For every \(c > 0\), there exists a connected graph \(G\) of arbitrarily large diameter such that \(\gamma (G\times G) < c\gamma (G)^2\). \item[2.] For any graphs \(G\) and \(H\), there exist graphs \(G^\prime\) and \(H^\prime\) containing \(G\) and \(H\), respectively, as induced subgraphs such that \(\gamma_{pr}(G^\prime\times H^\prime) \ge \frac{1}{2}\gamma_{pr}(G^\prime)\gamma_{pr}(H^\prime)\). \item[3.] For \(n \ge 71\) and let \(G_n = K_2 \square K_n\). Then \(\Gamma(G_n \times Gn) =n^2 = \Gamma(G_n)^2\). \end{itemize}