کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435326 | 689894 | 2016 | 18 صفحه PDF | دانلود رایگان |
• We reveal the relationship between conditional diagnosability and 2-extra connectivity of Graphs.
• The conditional diagnosability under the comparison model is equal to the 2-extra connectivity.
• As applications, these parameters are determined for some well-known classes of graphs.
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 tc(G)tc(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)κ2(G) of a graph G is the minimum number k for which there is a vertex-cut F with |F|=k|F|=k such that every component of G−FG−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 answers this problem by proving tc(G)=κ2(G)tc(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)(n,k)-star graphs, alternating group networks, (n,k)(n,k)-arrangement graphs, alternating group graphs, Cayley graphs obtained from transposition generating trees, bubble-sort graphs, k-ary n-cube networks, dual-cubes, pancake graphs and hierarchical hypercubes as well. Furthermore, many known results about these networks are obtained directly.
Journal: Theoretical Computer Science - Volume 627, 9 May 2016, Pages 36–53