在本篇論文中，給定一個圖形G以及一個非負整數 g , 而 g-超連接度是指在G中的一個最小基數點集合，假使存在這個點集合，當我們將此點集合，從圖G中移除，使得圖G會產生許多連通圖，而每一個連通圖的點數會大於 g 個節點。這個g-超連接度是一個通用且典型的連接度（connectivity）性質，並且針對現今大型平行系統提供可靠度以及容錯（fault-tolerance）標準。接下來介紹k元n立方體網路（k-ary n-cube networks），k元n立方體網路（k-ary n-cube networks）在建構多重程序系統中，是一個大家熟知的網路拓樸結構，可被標示為Qk/n。在本篇論文中，可知道k元n立方體網路（k-ary n-cube networks）的連接度（connectivity）為2n，我們證明k元n立方體網路（k-ary n-cube networks）的2-超連接度等於6n － 5 當k≥4以及n≥5。

Given a graph G and a non-negative integer g, the g-extraconnectivity of G is the minimum cardinality of a set of vertices in G, if exists, whose deletion disconnects G and every remaining component has more than g vertices. The g-extraconnectivity is a generalization of the classical connectivity and can provide more accurate measures for the reliability and the fault-tolerance of a large-scale parallel system. The k-ary n-cube, denoted by Qk/n is a well-known network topology for building multiprocessor systems. We show that for k≥4 and n≥5, the k-ary n-cube, whose connectivity is 2n, the 2-extraconnectivity is equal to 6n - 5.

[1] S. Abraham and K. Padmanabhan, "An analysis of the twisted cube topology," in Proceedings of the International conference on Parallel Processing, vol. 1, pp. 116-120, 1989.
[2] B. Bose, B. Broeg, Y. Kwon, and Y. Ashir, "Lee distance and topological properties of k-ary n-cubes," IEEE Transactions on Computers, vol. 44, no. 8, pp. 1021-1030, 1995.
[3] E. Cheng, L. Liptak,"A kind of conditional vertex connectivity of cayley graphs generated by transposition trees," Congressus Numerantium, in press.
[4] Y. C. Chen and J. M. Tan,"Restricted connectivity for three families of interconnection networks," Applied Mathematics and Computation vol. 188, pp.1848-1855, 2007.
[5] K. Day and A. E. Ai-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Transactions Parallel Distribution Systems, vol. 8, pp. 903-907, 1997.
[6] K. Day , "The conditional node connectivity of the k-ary n-cube," Journal of Interconnection Networks, vol. 5, No. 1, pp. 13-26, 2004.
[7] A. H. Esfahanian, "Generalized measures of fault tolerance with application to n-cube networks," IEEE Transactions on Computers, vol. 38, no. 11, pp. 1586-1591, 1989.
[8] J. Fàbrega and M. A. Fiol, "Extraconnectivity of graphs with large girth," Discrete Mathematics, vol. 127, pp. 163-170, 1994.
[9] J. Fàbrega and M. A. Fiol, "On the extraconnectivity of graphs ," Discrete Mathematics, vol. 155, pp. 49-57, 1996.
[10] S. A. Ghozati and H. C. Wasserman, "The k-ary n-cube network: modeling, topological properties and routing strategies," Computers and Electrical Engineering, vol. 25, no. 3, pp. 155-168, 1999.
[11] F. Harary, "Conditional connectivity," Networks, vol. 13, issue 3, pp. 347-357, 1983.
[12] S. C. Hu and C. B. Yang,"Fault tolerance on star graphs," Journal of Foundations of Computer Science, vol. 8, pp. 127-142, 1997.
[13] S.Y. Hsieh and T.J. Lin, "Embedding cycles and paths in a k-ary n-cube," in Proceedings of International Conference on Parallel and Distributed Systems, vol. 1, pp. 1-7, 2007.
[14] Sun-Yuan Hsieh and Tsong-Jie Lin, "Panconnectivity and Edge-Pancyclicity of k-Ary n-Cubes," Networks, vol. 54, issue 1, pp. 1-11, 2009.
[15] B.A. Izadi, F. Ozguner, "Design of a Circuit-switched highly fault-tolerant k-ary n-cube," Proc. 1997 Intl Conf. on Parallel Processing pp. 342-345, 1997.
[16] B. A. Izadi and F. Ozguner, "Enhanced Cluster k-Ary n-Cube, A Fault-Tolerant Multiprocessor," IEEE Transactions on Computers, vol. 52, issue 11, pp. 1443-1453, 2003.
[17] S. Lati¯, 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.
[18] M. J. Ma, G. Z. Liu, and J. M. Xu,"The super connectivity of augmented cubes," Information Processing Letters vol. 106 pp. 59-63, 2008.
[19] D. B. West, Introduction to Graph Theory, Prentice Hall Publishers, 2001.
[20] S. Y. Wang, J. Yuan, and A. X. Liu,"k-restricted edge connectivity for some interconnection networks," Applied Mathematics and Computation, vol. 201, issues.1-2, pp. 587-596, 2008.
[21] M. Wan, Z. Zhang,"A kind of conditional vertex connectivity of star graphs," Applied Mathematics Letters, vol.22, pp. 264-267, 2009.
[22] J. M. Xu, Topological structure and analysis of interconnection networks, Kluwer Academic Publishers, 2001.
[23] J. M. Xu, M. Xu, Q. Zhu,"The super connectivity of shuffle-cubes," Information Processing Letters, vol 96, pp. 123-127, 2005.
[24] 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.
[25] J. M. Xu, J. W. Wang, and W. W. Wang, "On super and restricted connectivity of some interconnection networks," Ars Combinatoria, vol. 94, 2010.
[26] W. H. Yang, J. Meng,"Extraconnectivity of hypercubes," Applied Mathematics Letters, vol. 22, pp. 887-891, 2009.
[27] W. H. Yang, H. Li, J. X. Meng,"Conditional connectivity of Cayley graphs generated by transposition trees," Information Processing Letters, vol. 110, pp. 1027-1030, 2010.
[28] Q. Zhu, J. M. Xu, M. Lv,Edge fault tolerance analysis of a class of interconnection networks," Applied Mathematics and Computation, vol. 172, pp. 111-121, 2006.
[29] Q. Zhu, J. M. Xu, X. Hou, M. Xu,"On reliability of the folded hypercubes," Information Sciences vol. 177, pp. 1782-1788, 2007.
[30] Q. Zhu,"On conditional diagnosability and reliability of the BC networks," The Journal of Super Computing vol. 45, pp. 173-184, 2008.