Domination criticality in product graphs (Q896090): Difference between revisions

Let \(G=(V,E)\) be a simple graph. A subset \(S\) of vertices of \(G\) is a dominating set if \(N[S]=V\) and is a connected dominating set if the induced subgraph \(G[S]\) is connected. The (connected) domination number \(\gamma(G) \) (\(\gamma_c(G)\)) is the minimum cardinality of a (connected) dominating set of \(G\). A graph \(G\) is \(k\mathrm{-}P\)-edge critical if \(P(G) = k\) and \(P(G + e) < k\) for each edge \(e\not \in E(G)\) and \(G\) is \(k-P\)-vertex critical if \(P(G) = k\) but for each vertex \(v\in G\), \(P(G - v) < k\) where \(P\in\{\gamma,\gamma_c\}\). The Cartesian product \(G\square H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V(G)\times V(H)\) and two vertices \((u_i,v_j) , (u_x,v_y)\) are adjacent if either \(u_i = u_x\) and \(v_jv_y\in E(H)\) or \(u_iu_x\in E(G)\) and \(v_j = v_y\). In this paper, the authors characterized all Cartesian product graphs \(G\) with \(\gamma_{c}(G) = 2, 3\). Also, they characterized the \(k-\gamma\)-vertex (edge) critical graphs and \(k-\gamma_c\)-vertex (edge) critical graphs for \(k = 2, 3\). The main results of this paper are: Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(2\mathrm{-}\gamma\)-vertex (edge) critical if and only if \(G=C_4\). Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(2\mathrm{-}\gamma_c\)-vertex (edge) critical if and only if \(G=C_4\). Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(3\mathrm{-}\gamma\)-vertex (edge) critical if and only if \(H_1=H_2=K_3\). Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(3\mathrm{-}\gamma_c\)-vertex (edge) critical if and only if \(H_1=H_2=K_3\).