Extra (component) connectivity and diagnosability of bubble sort networks
Hong Zhang, Shuming Zhou, Zhenqin Yu, Xiaoqing Liu · 2021 IEEE 21st International Conference on Software Quality, Reliability and Security Companion (QRS-C) · 2021
As generalizations of traditional connectivity (resp., diagnosability), h-component connectivity (resp., diagnosability) and h-extra connectivity (resp., diagnosability) are significant parameters to characterize invulnerability of multiprocessor systems. In this paper, we determine that h-extra connectivity of bubble sort networks$B_{n}$is$\kappa_{h}(B_{n})=(h+1)(n-1)-\frac{h(h+3)}{2}$for$0\leq h\leq\frac{n}{2}$. Afterwards, we show that h-extra diagnosability of$B_{n}$under PMC model and MM* model is$t^{h}(B_{n})=(h+1)(n- 1)-\frac{h(h+3)}{2}+h$. In addition, we show that$(h+1)$-component connectivity of$Bs_{n}$is$c\kappa_{h+1}(B_{n})=h(n-1)-\frac{h(h+1)}{2}+1$., and h-component diagnosability of$B_{n}$under PMC model and MM* model is$ct_{h}(B_{n})=h(n-1)-\frac{h(h+1)}{2}+1$for$1\leq h\leq\frac{n}{2}$.