Connectivity and Diagnosability of Leaf-Sort Graphs
Abstract
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 -dimensional leaf-sort graph has many good properties. In this paper, we prove that (a) is tightly super connected for odd and , and tightly super connected for even and ; (b) under the PMC model and MM model, the diagnosability for odd and , and for even and .
References
- 1. , Graph Theory (Springer, New York, 2007). Google Scholar
- 2. , An fault identification algorithm for diagnosable systems, IEEE Transactions on Computers 33(6) (1984) 486–492. Crossref, ISI, Google Scholar
- 3. , Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Transactions on Parallel and Distributed Systems 13(10) (2002) 1099–1104. Crossref, ISI, Google Scholar
- 4. , Algebra (Springer-Verlag, New York, 1974). Google Scholar
- 5. , A comparison connection assignment for self-diagnosis of multiprocessor systems, in Proceeding of 11th International Symposium on Fault-Tolerant Computing,
1981 , pp. 173–175. Google Scholar - 6. , On the connection assignment problem of diagnosable systems, IEEE Transactions on Computers EC-16 (1967) 848–854. Crossref, Google Scholar
- 7. , Connectivity and matching preclusion for leaf-sort graphs, Journal of Interconnection Networks 19(3) (2019) 1940007. Link, ISI, Google Scholar
- 8. , The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM model, IEEE Transactions on Parallel and Distributed Systems 26 (2015) 1165–1177. Crossref, ISI, Google Scholar


