Structural Properties and $t/s$ -Diagnosis for Star Networks Based on the PMC Model

Diagnosability is a key factor in the analysis of reliability for a network system. t/s-diagnosability is a novel measurement for evaluating the reliability of a system. In this paper, we derive some properties, which have not been reported by previous literatures, for a star network. By using these properties, we prove that an n-dimensional star graph (denoted by S_n) is [ln - (((l + 2)²)/3)]/([ln - (((l + 2)²)/3)] + l - 2)-diagnosable, where (n ≥ 5), 2 ≤ l ≤ n - 2. Furthermore, we prove that given an integer n(n ) 5), and another integer l(2 ≤ l ≤ n - 2), for some positive integer β ∈ ([(l - 1)n - (((l + 1)²)/3)], [ln - (((l + 2)²)/3)]], S_n is β/(β + l - 2)-diagnosable. In the last part of this paper, we propose an isolation-fast algorithm for S_n(n ≥ 5), and its time complexity is only O(N log₂N), where N = n!.