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

• DOI: 10.1016/j.tcs.2016.02.024
• Publication Date: 2016-02-23T09:20:02Z
• Authors: Rong-Xia Hao; Zeng-Xian Tian; Jun-Ming Xu
• Keywords: FOS: Mathematics; 0202 electrical engineering, electronic engineering, information engineering; Mathematics - Combinatorics; 0102 computer and information sciences; Combinatorics (math.CO); 02 engineering and technology; 01 natural sciences

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 $��_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)=��_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.