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

Abstract 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 κ h ( G ) and h-extra diagnosability t h m ˜ ( G ) of the regular connected graph G under MM* model, which is t h m ˜ ( G ) = κ h ( G ) + h . As an application, we directly obtain the h-extra diagnosability of star graph S n , alternating group graph network A N n and ( n , k ) -star graph S n , k by our proposed new result.