Connectivity and Super-Connectivity of Cartesian Product Graphs

Abstract

This paper determines that the connectivity of the Cartesian product $G_1\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{G}_2$ of two graphs $G_1$ and $G_2$ is equal to $min\{{\kappa }_1{v}_2+{\kappa }_2{v}_1,{\delta }_1+{\delta }_2\}$, where $v_i,{\kappa }_i$, and ${\delta }_i$ are the order, connectivity, and minimum degree of $G_i$, respectively, for $i=1,2$. Additionally, some necessary and sufficient conditions are given for $G_1\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{G}_2$ to be maximally connected and super-connected.