The 3-extra Connectivity and Faulty Diagnosability

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 tc(G) of G is the maximum number t for which G is conditionally t-diagnosable. The relationship between...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2018-05, Vol.61 (5), p.672-686
Main Authors: Gu, Mei-Mei, Hao, Rong-Xia, Feng, Yan-Quan, Yu, Ai-Mei
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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.
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/bxx089