The 3-extra Connectivity and Faulty Diagnosability
Mei-Mei Gu, Rong‐Xia Hao, Yan‐Quan Feng, Aimei Yu · The Computer Journal · 2017
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 tc(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 tc(G)=κ3(G)+1 or κ3(G)+2. As applications, we prove that tc(Γn(Δ)) = 8n−27 and κ3(Γn(Δ)) = 8n−28 for the Cayley graph generated by 2-tree Δ and that tc(Qn3) = 8n−11 for the 3-ary n-cubes Qn3.