Structure Fault Tolerance of Bubble-Sort Star Graphs

Abstract

As two significant performance indicators, structure connectivity and substructure connectivity have been widely studied, and they are used to judge a network’s fault tolerance properties from the perspective of the structure becoming faulty. An n-dimensional bubble-sort star graph BSn is a popular interconnection network with many good properties. We find the upper bounds of κ(BSn;K1,3) and κs(BSn;K1,3) in this paper. Furthermore, we establish κ(BSn;H) and κs(BSn;H) of BSn, where H∈{K1,K1,1,K1,2}.

Keywords

• connectivity
• bubble-sort star graph
• fault tolerance
• interconnection network
• structure connectivity