Connectivity and Diagnosability of Leaf-Sort Graphs
Mujiangshan Wang, Dong Xiang, Shiying Wang · Parallel Processing Letters · 2020
The connectivity and diagnosability of a multiprocessor system and an interconnection network are two important research topics. The system and the network have an underlying topology, which is usually presented by a graph. As a topology structure of interconnection networks, the [Formula: see text]-dimensional leaf-sort graph [Formula: see text] has many good properties. In this paper, we prove that (a) [Formula: see text] is tightly [Formula: see text] super connected for odd [Formula: see text] and [Formula: see text], and tightly [Formula: see text] super connected for even [Formula: see text] and [Formula: see text]; (b) under the PMC model and MM[Formula: see text] model, the diagnosability [Formula: see text] for odd [Formula: see text] and [Formula: see text], and [Formula: see text] for even [Formula: see text] and [Formula: see text].