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.