令Sn為維度n的星圖(n-star graph)的縮寫，還有一個強化版本的星圖，稱為(n,k)星圖((n,k)-star graph)，可縮寫成Sn,k， W.K.Chiang在1995年時提出此(n,k)-星圖的結構。在最近幾年，由於多處理器系統(multiprocessor system)快速的發展，一個系統內的處理器數量快速增加，導致多處理器系統的偵錯(diagnosis)變為極重要的一個議題。Lai介紹了一個新的偵錯理念，稱為條件偵錯度(conditional diagnosability)，在多處理器系統中，條件式偵錯相較於傳統的偵錯方式表現的更好，本篇論文即證明了在比較偵錯模式(comparison diagnosis model)下的(n,k)-星圖的條件偵錯度為n+2k－5，其中n ≥ 5， k ≥ 3，n – k ≥ 2。

Let Sn be the n-star graph with degree n, and there is an enhanced version of Sn, called (n,k)-star graph, denoted by Sn,k. The (n,k)-star graph was proposed in 1995 by W.K. Chiang et al. In recent years, diagnosis has been one of the most important issue as the size of multiprocessor system grows rapidly.
Conditional diagnosability is a new measure of diagnosability introduced by Lai et al. It is a better method to measure the diagnosability of regular interconnection networks. This thesis shows that the conditional diagnosability of (n,k)-star graph is n+2k-5, for n ≥ 5， k ≥ 3，n – k ≥ 2 under the comparison diagnosis model.

[1] S. B. Akers, B. Krishnamurthy, D. Harel, The star graph: an attractive alternative to the n-cube," in Proceedings of the International Conference on Parallel
Processing, pp.393-400, 1987.
[2] C. Balbuena, M. Cera, A. Dianez, P. Garcia-Vazquez, and X. Marcote, On the restricted connectivity and superconnectivity in graphs with given girth," Discrete
Mathematics, vol. 307, issue 6, pp. 659-667, 2007.
[3] D. Bauer, F. Boesch, C. Suffel, and R. Tindell, Connectivity extremal problems and the design of reliable probabilistic networks" in The theory and application of
graphs, pp.89-98, 1981.
[4] C.P. Chang, P.L. Lai, J.J.M. Tan, and L.H. Hsu, Diagnosability of t-Connected Networks and Product Networks under the Comparison Diagnosis Model" in IEEE
Transactions on Conputers, vol. 53, no. 12, pp.1582-1590, 2004.
[5] E. Cheng, M. J. Lipman, Increasing the connectivity of the star graphs" in Networks, pp. 165-169, 2002.
[6] G.Y. Chang, G.J. Chang, and G.H. Chen, Diagnosabilities of Regular Networks"
in IEEE Transaction Parallel and Distributed Systems, vol. 16, no. 4 , pp. 314-323,
2005.
[7] N. W. Chang and S. Y. Hsieh, Conditional diagnosability of augmented cubes under the PMC model," IEEE Transactions on Dependable and Secure Computing,
http://doi.ieeecomputersociety.org/10.1109/TDSC.2010.59.

[8] Y. C. Chen and J. J. M. Tan, Restricted connectivity for three families of interconnection networks," Applied Mathematics and Computation, vol. 188, issue 2,
pp. 1848-1855, 2007.
[9] W.K. Chiang, R.J. Chen, The (n,k)-star graph : A generalized star graph" in Information Processing Letters, pp. 259-264,1995.
[10] W.K. Chiang, R.J. Chen, Topological properties of the (n,k)-star graph," in International Journal of Foundations of Computer Science, Vol. 9, No. 2, pp.
235-248, 1998.
[11] Y.-Y. Chen, D.-R. Duh, T.-L. Ye, and J.-S. Fu, Weak-vertex-pancyclicity of (n,k)-star graphs," in Theoretical Computer Science, Vol. 396, pp. 191-199, 2008.
[12] E. P. Duarte JR, R. P. Ziwich, and L. C. P. Albini, A Survey of Comparison-Based System-Level Diagnosis," ACM Computing Surveys, vol. 43, no. 3, article
22, pp. 1-56, 2011.
[13] J. Fabrega and M. A. Fiol, Extraconnectivity of graphs with large girth," Discrete Mathematics, vol. 127, pp. 163-170, 1994.
[14] J. Fabrega and M. A. Fiol, On the extraconnectivity of graphs ," Discrete Mathematics, vol. 155, pp. 49-57, 1996.
[15] J. Fan, Diagnosability of crossed cubes under the two strategies," Chinese Journal of Computers, vol. 21, issue 5, pp. 456-462, 1998.
[16] J. Fan, Diagnosability of the Mobius cubes," IEEE Transactions on Parallel and Distributed Systems, vol. 9, issue 9, pp. 923-928, 1998.
[17] J. Fan, Diagnosability of Crossed Cubes under the Comparison Diagnosis Model" in IEEE Transsation Parallel and Distributed Systems, vol. 13, no. 7, pp. 687-692,
2002.

[18] F. Harary, Conditional connectivity," Networks, vol. 13, issue 3, pp. 347-357,
1983.
[19] W. S. Hong and S. Y. Hsieh, Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model," IEEE Transactions
on Reliability, accepted.
[20] S. Y. Hsieh and Y. S. Chen, Strongly diagnosable systems under the comparison diagnosis model," IEEE Transactions on Computers, vol. 57, issue 12, pp. 1720-
1725, 2008.
[21] S.Y. Hsieh, Y.S. Chen, Strongly Diagnosable Product Networks Under the Comparison Diagnosis Model" in IEEE Transactions on Computers, vol. 57, no. 6, pp.
721-732, 2008.
[22] S.Y. Hsieh, T.Y. Chuang, The Strong Diagnosability of Regular Networks and Product Networks under the PMC Model" in IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 3, pp. 367-378, 2009.
[23] S.Y. Hsieh, C.Y. Tsai, Extra Connectivity and Conditional Diagnosability of Folded Hypercubes" ,accepted
[24] S.Y. Hsieh, C.Y. Kao, Computing the Conditional Diagnosability of k-ary n-Cube Under the Comparison Diagnosis Model" ,accepted
[25] S.Y. Hsieh, T.Y. Lin, Computing the Conditional Diagnosability of k-ary n-Cube Under the PMC Model" ,accepted
[26] H. Hsu, Y. Hsieh, J. Tan, and L. Hsu, Fault hamiltonicity and fault hamiltonian connectivity of the (n,k)-star graphs" in Networks, Vol. 42, No. 4, pp. 189-201,
2003.

[27] G. H. Hsu and J. J. M. Tan, Conditional diagnosability of the BC networks under the comparison diagnosis model," International Computer Symposium, vol. 1, pp.
269-274, 2008.
[28] G. H. Hsu, C. F. Chiang, L. M. Shih,and J. J. M. Tan, Conditional diagnosability of hypercube under the comparison diagnosis model," Journal of Systems
Architecture, vol. 55, issue 2, pp. 140-146, 2009.
[29] A. Kavianpour, Sequential diagnosability of star graphs," Computers and Electrical Engineering, vol. 22, issue 1, pp. 37-44, 1996.
[30] A. Kavianpour and K. H. Kim, Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy," IEEE Transactions on Computers, vol. 40,
issue 2, pp. 232-237, 1991.
[31] A. Kavianpour and K. H. Kim, A comparative evaluation of four basic system-level diagnosis strategies for hypercubes," IEEE Transactions on Reliability, vol.
41, issue 1, pp. 26-37, 1992.
[32] S. Latifi, M. Hegde, and M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems," IEEE Transactions on Computers, vol. 43, no. 2,
pp. 218-222, 1994.
[33] C. W. Lee and S. Y.Hsieh, Determining the diagnosability of (1,2)-matching composition networks and its applications, in " IEEE Transactions on Dependable
and Secure Computing, vol. 8, issue 3, pp. 353-362, 2011.
[34] C. W. Lee and S. Y.Hsieh, Diagnosability of two-matching composition networks under the MM* model," IEEE Transactions on Dependable and Secure Computing,
vol. 8, issue 2, pp. 246-255, 2011.
[35] C.K. Lin, Jimmy J. M. Tan, L.H. Hsu, E. Cheng, and L. Liptak, Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees Under the
Comparison Diagnosis Model" in Interconnection Networks, vol. 9, pp. 83-97, 2008.

[36] J. Li, M. Chen, Y. Xiang, and S. Yao, Optimum broadcasting algorithms in (n,k)-star graphs using spanning trees" in IFIP International Federation for Information
Processing, pp. 220-230, 2007.
[37] P.L. Lai, Jimmy J.M. Tan,C.H. Tsai and L.H. Hsu, The diagnosability of the matching composition network under the comparison diagnosis model" in IEEE
Transactions on Conputers,vol.53, pp. 1064-1069, 2004.
[38] P.L. Lai, Jimmy J.M. Tan, Chien-Ping Chang, and Lih-Hsing Hsu, Conditional Diagnosability Measures for Large Multiprocessor Systems" in IEEE Transactions
on Conputers,vol.54, no.2, pp. 165-175, 2005.
[39] M. J. Ma, G. Z. Liu, and J. M. Xu, The super connectivity of augmented cubes,"Information Processing Letters, vol. 106, issue 2, pp. 59-63, 2008.
[40] J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessors systems," in Proceedings of the 11th International Symposium
on Fault-Tolerant Computing, pp. 173-175, 1981.
[41] M. Malek, A comparison connection assignment for diagnosis of multiprocessors systems," in Proceedings of the 7th International Symposium on Computer Architecture, pp. 31-36, 1980.
[42] F. P. Preparata, G. Metze, and R.T. Chien, On the connection assignment problem of diagnosis systems," IEEE Transactions on Electronic Computers, vol. 16,
issue 12, pp. 848-854, 1967.
[43] A. Sengupta, A. Dahbura, On self-diagnosable multiprocessor systems:diagnosis by comparison approach" in IEEE Transactions on Conputers, pp. 1386-
1396,1992.
[44] J. J. Sheu, W. T. Huang, and C. H. Chen, Strong diagnosability of regular networks under the comparison model," Information Processing Letters, vol. 106,
pp. 19-25, 2008.

[45] M. Wan and Z. Zhang, A kind of conditional vertex connectivity of star graphs," Applied Mathematics Letters, vol. 22, issue 2, pp. 264-267, 2009.
[46] D. Wang, "Diagnosability of Enhanced Hypercubes" in IEEE Transactions on Conputers, vol. 43, no. 9, pp. 1054-1061, 1994.
[47] D. Wang, Diagnosability of Hypercubes and Enhanced Hypercubes Under the Comparison Diagnosis Model" in IEEE Transactions on Conputers, vol. 48, no.
12, pp. 1369-1374, 1999.
[48] D. B. West, Introduction to Graph Theory, Prentice Hall Publishers, 2001.
[49] H. Whitney, Congruent graphs and the connectivity of graphs," Amer. J. Math.,
vol. 54, pp. 150-168, 1932.
[50] J. M. Xu, M. LÄu, M. J. Ma, and A. Hellwig, Super connectivity of line graphs," Information Processing Letters, vol. 94, issue 4, pp. 191-195, 2005.
[51] M. Xu, K. Thulasiraman, and X. D. Hu, Conditional diagnosability of matching composition networks under the PMC model," IEEE Transactions on Circuits and
Systems II, vol. 56, issue 11, pp. 875-879, 2009.
[52] J. M. Xu, J. W. Wang, and W. W. Wang, On super and restricted connectivity of some interconnection networks," Ars Combinatoria, vol. 94, 2010.
[53] J. M. Xu, Q. Zhu, and M. Xu, Fault-tolerant analysis of a class of networks,"Information Processing Letters, vol. 103, issue 6, pp. 222-226, 2007.
[54] M. Xu, X. Hu, Songpu. Shang, The Conditional Diagnosability of Shu²e-Cubes"in Jounal of system science and complexity, vol 23, pp. 81-90, 2010.
[55] X. Yang,D.J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices III," Int J Comput Math pp. 27-37, 2006.

[56] W. H. Yang and J. X. Meng, Extraconnectivity of hypercubes," Applied Mathematics Letters, vol. 22, issue 6, pp. 887-891, 2009.
[57] S. Zhou, The conditional diagnosability of MÄobius cubes under the comparison model," Proceedings of the 2009 IEEE International Conference on Information
and Automation, pp. 96-100, 2009.
[58] S. Zhou, The conditional diagnosability of locally twisted cubes," Proceedings of 2009 4th International Conference on Computer Science and Education, pp.
221-226, 2009.
[59] S. Zhou, The conditional diagnosability of twisted cubes under the comparison model," 2009 IEEE International Symposium on Parallel and Distributed Process-
ing with Applications, pp. 696-701, 2009.
[60] Q. Zhu, S.Y. Liu , M. Xu , On conditional diagnosability of the folded hypercubes" inInformation Sciences vol 178, pp. 1069-1077, 2008
[61] Q. Zhu, On conditional diagnosability and reliability of the BC networks" in The Journal of Supercomputing vol 45, no.2, pp. 173-184, 2008
[62] S. Zhou, L. Chen, Fault Tolerance of (n,k)-Star Graphs" in The 5th International Conference on Computer Science and Educations 2010.
[63] S. Zhou, W. Xiao, Conditional diagnosability of alternating group networks" in Information Processing Letters, pp. 403-409, 2010.
[64] S. Zhou, W. Xiao, The Conditional diagnosability of crossed cube under the comparison model" in International Journal of Computer Mathematis, pp. 3387-
3396, 2010.