2020/07/06 by Yulong Wei, Rong-Hua Li, Wei, Yulong +3
Computer Science · Engineering · #68M10 #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Primary 68M15 #Radiation Effects in Electronics #Secondary 05C82 #VLSI and Analog Circuit Testing
paper · pdf · doi:10.48550/arxiv.2007.03455
openalex publication_date 2020/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Zhu et al. [Theoret. Comput. Sci. 758 (2019) 1--8] introduced the h-edge tolerable diagnosability to measure the fault diagnosis capability of a multiprocessor system with faulty links. This kind of diagnosability is a generalization of the concept of traditional diagnosability. A graph is called a maximally connected graph if its minimum degree equals its vertex connectivity. It is well-known that many irregular networks are maximally connected graphs and the h-edge tolerable diagnosabilities of these networks are unknown, which is our motivation for research. In this paper, we obtain the lower bound of the h-edge tolerable diagnosability of a t-connected graph and establish the h-edge tolerable diagnosability of a maximally connected graph under the PMC model and the MM^* model, which extends some results in [IEEE Trans. Comput. 23 (1974) 86--88], [IEEE Trans. Comput. 53 (2004) 1582--1590] and [Theoret. Comput. Sci. 796 (2019) 147--153].