The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks

详细信息    查看全文

• 作者：Shiying Wang^a ; ^{wangshiying@htu.cn} ; ^{shiying@sxu.edu.cn} ; Zhenhua Wang^a ; Mujiangshan Wang^b
• 关键词：Interconnection network ; Connectivity ; Diagnosability ; Bubble-sort star graph
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：691-706
• 全文大小：861 K
• 卷排序：217

文摘

Connectivity plays an important role in measuring the fault tolerance of interconnection networks. The gg-good-neighbor connectivity of an interconnection network GG is the minimum cardinality of gg-good-neighbor cuts. Diagnosability of a multiprocessor system is one important study topic. A new measure for fault diagnosis of the system restrains that every fault-free node has at least gg fault-free neighbor vertices, which is called the gg-good-neighbor diagnosability of the system. As a famous topology structure of interconnection networks, the nn-dimensional bubble-sort star graph BSnBSn has many good properties. In this paper, we prove that 2-good-neighbor connectivity of BSnBSn is 8n−228n−22 for n≥5n≥5 and the 22-good-neighbor connectivity of BS4BS4 is 8; the 22-good-neighbor diagnosability of BSnBSn is 8n−198n−19 under the PMC model and MM∗∗ model for n≥5n≥5.