Portal de Periódicos da CAPES

The (n, k)-star graph: A generalized star graph

1995; Elsevier BV; Volume: 56; Issue: 5 Linguagem: Inglês

10.1016/0020-0190(95)00162-1

1872-6119

Wei‐Kuo Chiang, Chen Rong-Jaye,

Radiation Effects in Electronics

During the operation of large-scale multi-processor systems, intermittent failures have gradually become one of the major reliability challenge due to their unsustainable nature. The presence of intermittent faults usually complicates the diagnosis problem and may lead to incomplete diagnosis. As a result, the intermittent diagnosability of many interconnection networks are still uncertain, especially intermittent diagnosability under the MM* (Maeng and Malek) model. In this paper, under some conditions, we establish a new relationship between intermittent diagnosability and the minimum degree of a graph. As applications, the intermittent diagnosability of triangle-free graphs and graphs whose connectivity is equal to their minimum degree are determined, including BC (bijective connection) networks, exchanged hypercubes, exchanged crossed cubes, star graphs, folded hypercubes, augmented cubes, k-ary n-cubes, bubble-sort star graphs, split-star networks, etc., under the PMC (Preparata, Metze, and Chien) model and MM* model.