The 3-extra Connectivity and Faulty Diagnosability. (7th October 2017) - Gu, Mei-Mei; Hao, Rong-Xia; Feng, Yan-Quan; Yu, Ai-Mei
Abstract: The h -extra connectivity κ h ( G ) of G is the cardinality of a minimum set S such that G − S is disconnected and each component of G − S has at least h + 1 vertices. The conditional diagnosability t c ( G ) of G is the maximum number t for which G is conditionally t -diagnosable. The relationship between the extra connectivity and the conditional diagnosability under the MM model was discussed in [Theor. Comput. Sci. 618 (2016) 21–29] and [Theor. Comput. Sci. 627 (2016) 36–53]. The open problem that what is the relationship between the conditional diagnosability and the h -extra connectivity under the PMC model for some h was given in [Theor. Comput. Sci. 627 (2016) 36–53]. In this paper, we solve this problem for an n -regular n -connected graph G under certain conditions, and the relation is given by t c ( G ) = κ 3 ( G ) + 1 or κ 3 ( G ) + 2 . As applications, we prove that t c ( Γ n ( Δ )) = 8 n − 27 and κ 3 ( Γ n ( Δ )) = 8 n − 28 for the Cayley graph generated by 2-tree Δ and that t c ( Q n 3 ) = 8 n − 11 for the 3 -ary n -cubes Q n 3 .