Connectivity of Cartesian product graphs (Q817765): Difference between revisions

Let \(n(G)\), \(\kappa(G)\), \(\lambda(G)\) and \(\delta(G)\) be the order, connectivity, edge-connectivity and minimum degree of a (di-)graph, respectively. In addition, let \(G_1\times G_2\) be the Cartesian product of two (di-)graphs \(G_1\) and \(G_2\). If \(G_1,G_2\) are two connected graphs, then the authors prove that \(\kappa(G_1\times G_2)\geq\min\{\kappa(G_1)+\delta(G_2), \kappa(G_2)+\delta(G_1)\}\) and \(\lambda(G_1\times G_2)= \min\{\delta(G_1)+\delta(G_2),\lambda(G_1)n(G_2), \lambda(G_2)n(G_1)\}\) when \(G_i\neq K_1\) for \(i=1,2\). In the case that \(G_1,G_2\) are two strongly connected digraphs, it is shown that \(\kappa(G_1\times G_2)\geq\min\{\kappa(G_1)+\delta(G_2), \kappa(G_2)+\delta(G_1),2\kappa(G_1)+\kappa(G_2), 2\kappa(G_2)+\kappa(G_1)\}\). These results are also generalized to the Cartesian product of \(p\geq 3\) (di-)graphs.