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

Autor: Zeng-Xian Tian, Rong-Xia Hao, Jun-Ming Xu
Rok vydání: 2016
Předmět:
Zdroj: Theoretical Computer Science. 627:36-53
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2016.02.024
Popis: 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 answers 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, dual-cubes, pancake graphs and hierarchical hypercubes as well. Furthermore, many known results about these networks are obtained directly. 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.
Databáze: OpenAIRE
Externí odkaz: