Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs

DOI10.1016/J.TCS.2016.02.024zbMATH Open1338.68030arXiv1508.02173OpenAlexW1926802565MaRDI QIDQ265074FDOQ265074

Authors: Zeng-Xian Tian, Jun-Ming Xu, Rong-Xia Hao 

Publication date: 1 April 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The conditional diagnosability and the 2-extra connectivity are two important parameters to measure ability of diagnosing faulty processors and fault-tolerance in a multiprocessor system. The conditional diagnosability $t_c(G)$ of $G$ is the maximum number $t$ for which $G$ is conditionally $t$-diagnosable under the comparison model, while the 2-extra connectivity $kapp{a}_2(G)$ of a graph $G$ is the minimum number $k$ for which there is a vertex-cut $F$ with $|F|=k$ such that every component of $G-F$ has at least $3$ vertices. A quite natural problem is what is the relationship between the maximum and the minimum problem? This paper partially answer this problem by proving $t_c(G)=kapp{a}_2(G)$ for a regular graph $G$ with some acceptable conditions. As applications, the conditional diagnosability and the 2-extra connectivity are determined for some well-known classes of vertex-transitive graphs, including, star graphs, $(n,k)$-star graphs, alternating group networks, $(n,k)$-arrangement graphs, alternating group graphs, Cayley graphs obtained from transposition generating trees, bubble-sort graphs, $k$-ary $n$-cube networks and dual-cubes. Furthermore, many known results about these networks are obtained directly.

Full work available at URL: https://arxiv.org/abs/1508.02173

Recommendations

• The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model
• Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model
• The \(g\)-extra conditional diagnosability of graphs in terms of \(g\)-extra connectivity
• Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs
• Conditional diagnosability of the \(\mathit{SP}_n\) graphs under the comparison diagnosis model

zbMATH Keywords

Cayley graphcomparison modelconditional diagnosabilityextra connectivitymax-min problemsymmetric graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cites Work

• Arrangement graphs: A class of generalized star graphs
• The \((n,k)\)-star graph: A generalized star graph
• A kind of conditional fault tolerance of alternating group graphs
• Conditional connectivity of Cayley graphs generated by transposition trees
• On the extraconnectivity of graphs
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• 3-extra connectivity of 3-ary \(n\)-cube networks
• Principles of combinatorics
• On the arrangement graph.
• Conditional fault diagnosability of dual-cubes
• A survey of comparison-based system-level diagnosis
• Fault-tolerance of \((n, k)\)-star networks
• Title not available (Why is that?)
• A group-theoretic model for symmetric interconnection networks
• Title not available (Why is that?)
• The conditional fault diagnosability of \((n, k)\)-star graphs
• Diagnosability of enhanced hypercubes
• Extraconnectivity of \(k\)-ary \(n\)-cube networks
• Theory and Application of Graphs
• On deriving conditional diagnosability of interconnection networks
• Conditional fault diagnosis of hierarchical hypercubes
• Characterizing a kind of fault tolerance of alternating group network
• Fault diagnosability of arrangement graphs
• Conditional Diagnosability of Alternating Group Graphs
• A new class of interconnection networks based on the alternating group
• On self-diagnosable multiprocessor systems: diagnosis by the comparison approach
• The super connectivity of the pancake graphs and the super laceability of the star graphs
• Conditional diagnosability of alternating group networks
• On the embedding of cycles in pancake graphs

Cited In (31)

• Probabilistic diagnosis of clustered faults for hypercube-based multiprocessor system
• The 1-good neighbor connectivity of unidirectional star graph networks
• The extra connectivity of the enhanced hypercubes
• The non-inclusive diagnosability of regular graphs
• The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model
• Fault diagnosability of DQcube under the PMC model
• The \(g\)-extra conditional diagnosability of graphs in terms of \(g\)-extra connectivity
• The Component Diagnosability of General Networks
• Fault diagnosability of bicube networks under the PMC diagnostic model
• A new proof for exact relationship between extra connectivity and extra diagnosability of regular connected graphs under MM* model
• The extra connectivity and extra diagnosability of regular interconnection networks
• Reliability evaluation of half hypercube networks
• Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs
• Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model
• Characterization of component diagnosability of regular networks
• Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks
• The \(R_g\)-conditional diagnosability of international networks
• Fault tolerance analysis of hierarchical folded cube
• The \(g\)-good neighbor conditional diagnosability of twisted hypercubes under the PMC and MM* model
• Measurement and algorithm for conditional local diagnosis of regular networks under the \(\mathrm{MM}^\ast\) model
• Relationship between extra edge connectivity and component edge connectivity for regular graphs
• On computing of a conditional edge connectivity of alternating group network
• The diagnosability of wheel networks with the condition: 2-extra
• Conditional diagnosability of the \(\mathit{SP}_n\) graphs under the comparison diagnosis model
• Conditional diagnosability of multiprocessor systems based on Cayley graphs generated by transpositions
• Reliability of \((n,k)\)-star network based on \(g\)-extra conditional fault
• Conditional diagnosability of Cayley graphs generated by wheel graphs under the PMC model
• Parallel routing in regular networks with faults
• Hybrid fault diagnosis capability analysis of regular graphs
• Estimating the subsystem reliability of bubblesort networks
• The \(g\)-good-neighbor diagnosability of \((n,k)\)-star graphs

This page was built for publication: Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q265074)