Paper Info
Title
The 3-extra Connectivity and Faulty Diagnosability.
Abstract
The h-extra connectivity k(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) = k(3)(G) + 1 or k(3)(G) + 2. As applications, we prove that t(c)(Gamma(n)(Delta)) = 8n - 27 and k(3) (Gamma(n) (Delta)) = 8n -28 for the Cayley graph generated by 2-tree Delta and that t(c)(Q(n)(3)) = 8n - 11 for the 3-ary n-cubes Q(n)(3).
Year
DOI
Venue
2018
10.1093/comjnl/bxx089
COMPUTER JOURNAL
Keywords
Field
DocType
fault-tolerance,extra connectivity,conditional diagnosability,PMC model,regular graph,interconnection network
Computer science,Theoretical computer science,Distributed computing
Journal
Volume
Issue
ISSN
61
5
0010-4620
Citations 
PageRank 
References 
0
0.34
37
Authors
4
Name
Order
Citations
PageRank
Mei-Mei Gu13710.45
Rongxia Hao216526.11
Yan-quan Feng335041.80
Aimei Yu402.37