Extraconnectivity of Cartesian Product Graphs of Paths

Abstract

Given a graph $G$ and a non-negative integer $g$, the $g$-extra-connectivity of $G$ (written ${\kappa }_g(G)$) is the minimum cardinality of a set of vertices of $G$, if any, whose deletion disconnects $G$, and every remaining component has more than $g$ vertices. The usual connectivity and superconnectivity of $G$ correspond to ${\kappa }_0(G)$ and ${\kappa }_1(G)$, respectively. In this paper, we determine ${\kappa }_g(P_{n_1}\times P_{n_2}\times \cdots \times P_{n_s})$ for $0\le g\le s$, where $\times$ denotes the Cartesian product of graphs. We generalize ${\kappa }_g(Q_n)$ for $0\le g\le n$, $n\ge 4$, where $Q_n$ denotes the $n$-cube.