The Extra Connectivity, Extra Conditional Diagnosability, and t/m-Diagnosability of Arrangement Graphs

Extra connectivity is an important indicator of the robustness of a multiprocessor system in presence of failing processors. The g-extra conditional diagnosability and the t/m-diagnosability are two important diagnostic strategies at system-level that can significantly enhance the system's self-diagnosing capability. The g-extra conditional diagnosability is defined under the assumption that every component of the system removing a set of faulty vertices has more than g vertices. The t/m-diagnosis strategy can detect up to t faulty processors which might include at most m misdiagnosed processors, where m is typically a small integer number. In this paper, we analyze the combinatorial properties and fault tolerant ability for an (n,k)-arrangement graph, denoted by A{n,k}, a well-known interconnection network proposed for multiprocessor systems. We first establish that the A{n,k} 's one-extra connectivity is (2k-1) (n-k)-1 (k≥ 3, n≥ k+2), two-extra connectivity is (3k-2)(n-k)-3 ( k≥ 4, n≥ k+2), and three-extra connectivity is (4k-4)(n-k)-4 (k≥ 4, n≥ k+2 or k≥ 3, n≥ k+3), respectively. And then, we address the g-extra conditional diagnosability of A{n,k} under the PMC model for 1≤ g ≤ 3. Finally, we determine that the (n,k)-arrangement graph A-{n,k} is [(2k-1)(n-k)-1]/1-diagnosable (k≥ 4, n≥ k+2), [(3k-2)(n-k)-3]/2-diagnosable ( k≥ 4, n≥ k+2), and [(4k-4)(n-k)-4]/3-diagnosable (k≥ 4, n≥ k+3) under the PMC model, respectively.