The structure fault tolerance of burnt pancake networks

Abstract

One of the symbolic parameters to measure the fault tolerance of a network is its connectivity. The HH-structure connectivity and HH-substructure connectivity extend the classical connectivity and are more practical. For a graph GG and its connected subgraph HH, the HH-structure connectivity κ(G;H)\kappa \left(G;\hspace{0.33em}H) (resp. HH-substructure connectivity κs(G;H){\kappa }^{s}\left(G;\hspace{0.33em}H)) of GG is the cardinality of a minimum subgraph set such that every element of the set is isomorphic to HH (resp. every element of the set is isomorphic to a connected subgraph of HH) in GG, whose vertices removal disconnects GG. In this article, we investigate the HH-structure connectivity and HH-substructure connectivity of the nn-dimensional burnt pancake network BPn{{\rm{BP}}}_{n} for each H∈{K1,K1,1,…,K1,n−1,P4,…,P7,C8}H\in \left\{{K}_{1},{K}_{1,1},\ldots ,{K}_{1,n-1},{P}_{4},\ldots ,{P}_{7},{C}_{8}\right\}.

Keywords

• interconnection networks
• h-structure connectivity
• h-substructure connectivity
• burnt pancake networks
• 05c05
• 05c25
• 05c38
• 05c40