Extraconnectivity of Folded Hypercubes

Abstract

Given a graph \(G\) and a non-negative integer \(g\), the \(g\)-extra-connectivity of \(G\), denoted by \(\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. Note that \(\kappa_0(G)\) and \(\kappa_1(G)\) correspond to the usual connectivity and restricted vertex connectivity of \(G\), respectively. In this paper, we determine \(\kappa_g(FQ_n)\) for \(0 \leq g \leq n-4\), \(n \geq 8\), where \(FQ_n\) denotes the \(n\)-dimensional folded hypercube.