A new proof for exact relationship between extra connectivity and extra diagnosability of regular connected graphs under MM* model

The extra connectivity and extra diagnosability are two important measures for network reliability. Under MM* model, two possible relationships between extra connectivity and extra diagnosability were proposed in Reference [24]. However, there are some shortcomings in it: (1) the conclusion of Theorem 3.9 is wrong; (2) the corresponding proof of Theorem 3.9 is flawed; (3) the exact relationship is still not clear. In this paper, we impose reasonable constraints, and give a new and correct proof for measuring, the exact relationship between h-extra connectivity kappa(h)(G) and h-extra diagnosability t(h)((m) over tilde)(G) of the regular connected graph G under MM* model, which is t(h)((m) over tilde) (G) = kappa(h) (G) + h. As an application, we directly obtain the h-extra diagnosability of star graph S-n, alternating group graph network AN(n) and (n, k)-star graph S-n,S-k by our proposed new result. (C) 2020 Elsevier B.V. All rights reserved.