Paper Info
Title
The pessimistic diagnosabilities of some general regular graphs.
Abstract
The pessimistic diagnosis strategy is a classic strategy based on the PMC model. A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G, denoted by tp(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. In this paper, we study the pessimistic diagnosabilities of some general k-regular k-connected graphs Gn. The main result tp(Gn)=2k−2−g under some conditions is obtained, where g is the maximum number of common neighbors between any two adjacent vertices in Gn. As applications of the main result, every pessimistic diagnosability of many famous networks including some known results, such as the alternating group networks ANn, the k-ary n-cubes Qnk, the star graphs Sn, the matching composition networks G(G1,G2;M) and the alternating group graphs AGn, are obtained.
Year
DOI
Venue
2016
10.1016/j.tcs.2015.10.025
Theoretical Computer Science
Keywords
Field
DocType
Pessimistic diagnosability,PMC model,Regular graph,Interconnection network
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Regular graph,Mathematics,Alternating group,Bounded function
Journal
Volume
Issue
ISSN
609
P2
0304-3975
Citations 
PageRank 
References 
8
0.51
24
Authors
3
Name
Order
Citations
PageRank
Rongxia Hao116526.11
Mei-Mei Gu280.51
Yan-quan Feng335041.80