The 3-extra Connectivity and Faulty Diagnosability. (7th October 2017)

• Record Type: Journal Article
• Authors: Gu, Mei-Mei; Hao, Rong-Xia; Feng, Yan-Quan; Yu, Ai-Mei
• Is Part Of: Computer journal. Volume 61:Number 5(2018)
• Page Start: 672
• Page End: 686
• Publication Date: 2017-10-07
• Subjects: fault–tolerance -- extra connectivity -- conditional diagnosability -- PMC model -- regular graph -- interconnection network; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx089
• Languages: English
• ISSNs: 0010-4620

Abstract

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 .