Submit Manuscript  

Article Details


Diagnosability of Alternating Group Graphs with Missing Edges

[ Vol. 11 , Issue. 1 ]

Author(s):

Shiying Wang* and Xiaolei Ma   Pages 51 - 57 ( 7 )

Abstract:


Background: Many multiprocessor systems have interconnection networks as underlying topologies and an interconnection network is usually represented by a graph where nodes represent processors and links represent communication links between processors.

Methods: The diagnosability of the system plays an important role in measuring the fault tolerance of the interconnection network. The n -alternating group graph has many favorable properties such as vertex and edge symmetry, recursive structure, high connectivity, small diameter and average distance, etc., which make it favorable as a network topology for the system.

Results: The diagnosability of an interconnection network G is less than or equal to the minimum degree of G . G has the strong local diagnosaility property if the local diagnosability of every vertex equals to its degree in G . In this paper, we prove that the n -alternating group graph has the strong local diagnosability property even if there exist (2n - 7) missing edges in it under the MM* model.

Conclusion: In this paper, we studied the diagnosis of an n -dimensional alternating group graph n AG under the MM* model. We proved that n AG has the strong local diagnosability property, and keeps this strong property even if there exists up to (2n - 7) missing edges in it. As a result, the diagnosability of n AG with arbitrary missing links can be obtained as the minimum value among the remaining degree of every processor, provided that the cardinality of the set of missing links does not exceed 2n - 7 .

Keywords:

Interconnection network, combinatorics, diagnosability, alternating group graph, MM* model, vertex.

Affiliation:

Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007

Graphical Abstract:



Read Full-Text article