處理器的錯點偵測，在多處理器系統可靠性上扮演著很重要的角色。目前有許多偵測錯點的模型被提出，此篇的PMC 模型即是被廣泛應用的模型之一。條件偵錯度是一個能夠在確保系統內不存在一個所有相鄰點皆為錯點的情況下，保證能夠偵測出的錯點個數。此篇論文證明了在(n ≥ 4, k = 1),( n ≥ 5, 2 ≤ k ≤ n – 3), (n ≥ 5, k = n - 2)等情況下，(n,k)-星圖的條件偵錯度。

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system; the diagnosability of many well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a metric that can give the maximum number of conditional faulty set that the system is guaranteed to identify. It is impossible that all adjacent vertices of one vertex are faulty simultaneously. This thesis shows that the conditional diagnosability of (n,k)-star graphs for (n ≥ 4, k = 1) and (n ≥ 5, 2 ≤ k ≤ n - 3) and (n ≥ 5, k = n - 2) under the PMC model .

[1] S. B. Akers, D. Horel, B. Krishnamurthy, "The star graph: an attractive alternative to the n-cube", in Proc. Int'l Conf: Parallel Processing, pp. 393-400, 1987.
[2] S. B. Akers, B. Krishnamurthy, "A group-theoretic model for symmetric interconnection networks", IEEE Trans: Computers, vol. 38, no. 4, pp. 555-566, 1989.
[3] N. W. Chang, W. H. Deng, S. Y. Hsieh, "Conditional diagnosability of (n, k)-star networks under the comparison diagnosis model", IEEE Trans: Reliability, pp.
1-12, 2014.
[4] N. W. Chang, S. Y. Hsieh, "Conditional diagnosability of augmented cubes under the PMC model", IEEE Trans: Dependable and Secure Computing, vol. 9, no. 1, pp. 46-60, 2012.
[5] N. W. Chang, S. Y. Hsieh, "Structural properties and conditional diagnosability of star graphs by using the PMC model", IEEE Trans: Parallel Distrib: Syst:, vol. 25 no. 11, pp. 3002-3011, 2014.
[6] N. W. Chang, T. Y. Lin, S. Y. Hsieh, "Conditional diagnosability of k-ary n-cubes under the PMC model", ACM Trans: Design Autom: Electron: Syst:, vol. 17, no. 4, pp. 46, 2012.
[7] Y. Y. Chen, D. R. Duh, T. L. Ye, J. S. Fu, "Weak-vertex-pancyclicity of (n, k)-star graphs", Theoretical Computer Science, vol. 396, no. 1-3, pp. 191-199, 2008.
[8] W. K. Chiang, R. J. Chen, "The (n, k)-star graph : a generalized star graph", Inf: Process: Lett:, vol. 56, no. 5, pp. 259-264, 1995.
[9] W. K. Chiang, R. J. Chen, "Topological properties of the (n, k)-star graph", Int: J: Found: Comput: Sci:, vol. 9, no. 2, pp. 235-248, 1998.
[10] A. T. Dahbura, G. M. Masson, "An O(n^2.5) fault identi cation algorithm for diagnosable systems", IEEE Trans: Computers, vol. 33, no. 6, pp. 486-492, 1984.
[11] J. Fan, "Diagnosability of crossed cubes under the comparison diagnosis model", IEEE Trans: Parallel and Distributed Systems, vol. 13, no. 7, pp. 687-692, 2002.
[12] S. Y. Hsieh, C. Y. Kao, "The Conditional diagnosability of k-ary n-cubes under the comparison diagnosis model", IEEE Trans: Computers, vol. 62, no. 4, pp. 839-843, 2013.
[13] G. H. Hsu, C. F. Chiang, L. M. Shih, L. H. Hsu, J. J. M. Tan, "Conditional diagnosability of hypercubes under the comparison diagnosis model", J: Systems Architecture, vol. 55, no. 2, pp. 140-146, 2009.
[14] H. Hsu, Y. Hsieh, J. Tan, L. Hsu, "Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)-star graphs", Networks, vol. 42, no. 4, pp. 189-201, 2003.
[15] P. L. Lai, J. J. M. Tan, C. P. Chang, L. H. Hsu, "Conditional diagnosability measures for large multiprocessor systems", IEEE Trans: Computers, vol. 54, no. 2, pp. 165-175, 2005.
[16] L. Lin , S. Zhou, L. Xu, D. Wang, "Conditional diagnosability of arrangement graphs under the PMC model", Theoretical Computer Science. vol. 548, pp. 79-97, 2014.
[17] J. Maeng, M. Malek, "A comparison connection assignment for self-diagnosis of multiprocessor systems", in Proc: 11th Int'l Symp: Fault-Tolerant Computing, pp.173-175, 1981.
[18] S. L. Peng, C. K. Lin, J. J. M. Tan, L. H. Hsu, "The g-good-neighbor conditional diagnosability of hypercube under PMC model", Appl: Math: Computat:, vol. 218, no. 21, pp. 10406-10412, 2012.
[19] F. P. Preparata, G. Metze, R. T. Chien, "On the connection assignment problem of diagnosable systems", IEEE Trans: Computers, vol. 16, no. 6, pp. 448-454,1967.
[20] A. Sengupta, A. T. Dahbura, "On self-diagnosable multiprocessor systems: diagnosis by the comparison approach", IEEE Trans: Computers, vol. 41, no. 11, pp. 1386-1396, 1992.
[21] W. H. Yang, H. Z. Li, X. F. Guo, "A kind of conditional fault tolerance of the (n, k)-star graphs", Inf: Process: Lett:, vol. 110, no. 22, p.p. 1007-1011, 2010.
[22] S. Zhou, "The conditional fault diagnosability of (n, k)-star graphs", Appl: Math: Computat:, vol. 218, no. 19, pp. 9742-9749, 2012.