The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model

Title: The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model
Creator: Wang, Mujiangshan; Guo, Yubao; Wang, Shiying
Relation: International Journal of Computer Mathematics Vol. 94, Issue 3, p. 620-631
Publisher Link: http://dx.doi.org/10.1080/00207160.2015.1119817
Publisher: Taylor & Francis
Resource Type: journal article
Date: 2017
Description: Diagnosability is an important metric for measuring the reliability of multiprocessor systems. In 2012, Peng et al. proposed a new measure for fault tolerance of the system, which is called g-good-neighbour diagnosability that restrains every fault-free node containing at least g fault-free neighbours. As a favourable topology structure of interconnection networks, the Cayley graph CΓ_n generated by the transposition tree Γ_n has many good properties. In this paper, we give that the 1-good-neighbour diagnosability of CΓ_n under the PMC model and MM∗ model is 2_n−3 except the bubble-sort graph B₄ under MM∗ model, where n≥4, and the 1-good-neighbour diagnosability of B₄ under the MM∗ model is 4.
Subject: interconnection network; graph; diagnosability; PMC model; MM* model; Cayley graph; 1-Good-neighbour diagnosability
Identifier: http://hdl.handle.net/1959.13/1390066
Identifier: uon:32988
Identifier: ISSN:0020-7160
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format