The extra connectivity of the enhanced hypercubes

Abstract As one of the best parameters to evaluate the fault tolerance of interconnection networks, extra connectivity plays an important role in multiprocessor systems for reliable computing. Given a graph G and a non-negative integer g, the g-extra connectivity (resp. g-extra edge connectivity) of G, denoted by κ g ( G ) (resp. λ g ( G ) ), is the minimum cardinality of a set of vertices (resp. edges) in G, if exists, whose deletion disconnects G and leaves each remaining component with at least g + 1 vertices. In this paper, we determine κ g ( Q n , k ) and λ g ( Q n , k ) of the enhanced hypercube Q n , k for g = 1 , 2 . Furthermore, as the byproduct of our results, we determine the conditional diagnosability of Q n , k under the comparison model and PMC model.