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 \leq g \leq s\), where \(\times\) denotes the Cartesian product of graphs. We generalize \(\kappa_g(Q_n)\) for \(0 \leq g \leq n\), \(n \geq 4\), where \(Q_n\) denotes the \(n\)-cube.