The h-Extra Edge-Connectivity of Hierarchical Pancake Graphs

Extra edge-connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. For a graph [Formula: see text], the [Formula: see text]-extra edge-connectivity of [Formula: see text] is the minimum cardinality of a set of edges in [Formula: see text], if exists, whose deletion disconnects [Formula: see text] and leaves every remaining component with at least [Formula: see text] vertices. The hierarchical pancake graph [Formula: see text] is a new interconnection topology structure, which uses the pancake graphs as building blocks. In this paper, we determine the [Formula: see text]-extra edge-connectivity of hierarchical pancake graph [Formula: see text] for [Formula: see text].