Star structure fault tolerance of Bicube networks

Abstract

Processor and communication link failures are inevitable in a large multiprocessor system, and so the fault tolerance of its underlying interconnection network has become a key scientific issue. Connectivity is an important parameter to characterize network fault tolerance, and there are many novel variants of classical connectivity to measure the fault tolerance of interconnection networks. However, these new strategies only consider a single faulty vertex. Structure connectivity and substructure connectivity make up for this deficiency, which underline the fault situation with certain specific structures. H-structure-connectivity $\kappa (G;H)$ (resp. H-substructure-connectivity ${\kappa }^s(G;H)$) of G is the minimum cardinality of H-structure-cuts (resp. H-substructure-cuts). For the n-dimensional Bicube network $B{Q}_n$, we establish the structure and substructure connectivity of Bicube networks, i.e. $\kappa (B{Q}_n;K_{1,1})={\kappa }^s(B{Q}_n;K_{1,1})=n$ for odd $n\ge 5$; $\kappa (B{Q}_n;K_{1,1})={\kappa }^s(B{Q}_n;K_{1,1})=n-1$ for even $n\ge 4$ and $\kappa (B{Q}_n;K_{1,r})={\kappa }^s(B{Q}_n;K_{1,r})=\lceil \frac{n}{2}\rceil$ for $n\ge 6$ and $2\le r\le n-1$.

Keywords:

• Interconnection network
• fault tolerance
• structure connectivity
• substructure connectivity
• Bicube networks

Acknowledgments

The authors would like to express their sincere gratitude to all reviewers for valuable suggestions, which are helpful in improving and clarifying the original manuscript. We thank the National Institute of Education, Nanyang Technological University, where part of this research was performed.

Availability of data

No data was used in the preparation of this manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was partly supported by the National Natural Science Foundation of China (Nos. 61977016 and 61572010), Natural Science Foundation of Fujian Province (Nos. 2020J01164, 2017J01738). This work was also partly supported by Fujian Alliance of Mathematics (No. 2023SXLMMS04) and China Scholarship Council (CSC No. 202108350054).