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

Title: The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks
Creator: Wang, Shiying; Wang, Zhenhua; Wang, Mujiangshan
Relation: Discrete Applied Mathematics Vol. 217, Issue Part 3, p. 691-706
Publisher Link: http://dx.doi.org/10.1016/j.dam.2016.09.047
Publisher: Elsevier
Resource Type: journal article
Date: 2017
Description: Connectivity plays an important role in measuring the fault tolerance of interconnection networks. The g-good-neighbor connectivity of an interconnection network G is the minimum cardinality of g-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 fault-free neighbor vertices, which is called the -good-neighbor diagnosability of the system. As a famous topology structure of interconnection networks, the n-dimensional bubble-sort star graph BS_n has many good properties. In this paper, we prove that 2-good-neighbor connectivity of BS_n is 8n - 22 for n ≥ 5 and the 2-good-neighbor connectivity of BS₄ is 8; the 2-good-neighbor diagnosability of BS_n is 8n - 19 under the PMC model and MM* model for n ≥ 5.
Subject: interconnection network; connectivity; diagnosability; bubble-sort star graph
Identifier: http://hdl.handle.net/1959.13/1385174
Identifier: uon:32182
Identifier: ISSN:0166-218X
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format