給定一個圖形G以及一個非負整數h，h-限制連通度是指在圖G中有一個最小點數集合X，其中X為圖G的子圖，使得當圖G扣除掉子圖X時，剩餘的連通圖互不相連並且在剩餘的連通圖中的任何一個點都至少有h個鄰居，將此定義為kh(G)。摺疊式超立方體是一個眾所皆知的網路拓樸結構，摺疊式超立方體能夠從超立方體中加上一種特殊的連接方式而得。在本篇論文中，我們證明摺疊式超立方體的3-限制連通度為8n − 16當n≥6.

Given a graph G = (V,E), where V is the node set and E is the edge set of G, and a non-negative integer h, the h-restricted connectivity of G is the minimum size of a set of nodes X of G, where X ⊂ V (G), such that G[V − X] is disconnected and each node in the remaining graph has at least h neighbors, denoted by kh(G). Folded hypercube FQ is a well-known network topology. An n-dimensional folded hypercube FQn can be obtained from an n-dimensional hypercube by adding a specific perfect matching. In this thesis, we show that 3-restricted connectivity of n-dimensional folded hypercube is 8n − 16 for n ≥ 6.

[1] N.W. Chang and S.Y. Hsieh, “{2,3}-Extraconnectivities of hypercube-like networks,” Journal of Computer and System Sciences, 79 (5): 669–688, 2013.

[2] N.W. Chang, C.Y. Tsai and S.Y. Hsieh, “On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes,” IEEE Transactions on Computers, 63(6): 1593–
1599, 2014.

[3] Y.C. Chen and J.M. Tan, “Restricted connectivity for three families of interconnection network,” Applied Mathematics and Computation, 188: 1848–1855, 2007.

[4] K. Day and A.E. Ai-Ayyoub, “The conditional node connectivity of the k-ary n-cube networks,” IEEE Transactions Parallel Distribution System, 5(1): 13–26, 2004.

[5] A. El-Amawy and S. Latifi, “Properties and performance of folded hypercubes,” IEEE Transactions Parallel Distribution System, 2: 31–42, 1991.

[6] A.H. Esfahanian, “Generalized measures of fault tolerance with application to n-cube,” IEEE Transactions on Computers, 38(11): 1586–1591, 1989.

[7] J. Fabrega and M.A. Fiol, “Extraconnectivity of graphs with large girth,” Discrete Mathematics, 127: 163–170, 1994.

[8] J. Fabrega and M.A. Fiol, “On the extraconnectivity of graphs,” Discrete Mathematics, 155: 49–57, 1996.

[9] J. Fan, S. Zhang, X. Jia and G. Zhang, “The restricted connectivity of locally twisted cubes,” Pervasive Systems, Algorithms, and Networks, 574–578, 2009.

[10] F. Harary, “Conditional connectivity,” Networks, 13(3): 347–357, 1983.

[11] W.S. Hong and S.Y. Hsieh, “Extra edge connectivity of hypercube-like networks,” International Journal of Parallel, Emergent and Distributed Systems, 28(2): 123–133, 2013.

[12] S.Y. Hsieh and Y.H. Chang, “Extraconnectivity of k-ary n-cube networks,” Theoretical Computer Science, 443(20): 63–69, 2012.

[13] S.Y. Hsieh, H.W. Huang and C.W. Lee, “{2, 3}-restricted connectivity of locally twisted cubes,” Theoretical Computer Science, 615: 78–90, 2016.

[14] S.C. Hu and C.B. Yang, “Fault tolerance on star graphs,” Foundations of Computer Science, 8: 127–142, 1997.

[15] S. Latifi, M. Hegde and M. Naraghi-Pour, “Conditional connectivity measures for large multiprocessor systems,” IEEE Transactions on Computers, 43: 218-222, 1994.

[16] L. Lin, L. Xu, S. Zhou and S.Y. Hsieh, “The Extra, Restricted Connectivity and Conditional Diagnosability of Split-Star Networks,” IEEE Transactions on Parallel
Distributed Systems, 27(2): 533–545, 2016.

[17] M.J. Ma, G.Z. Liu and J.M. Xu, “The super connectivity of augmented cubes,” Information Processing Letters, 106: 59–63, 2008.

[18] J.X. Meng, “Optimally super-edge-connected transitive graphs,” Discrete Mathematics, 260(1): 239–248, 2003.

[19] J.X.Meng and Y.H. Ji, “On a kind of restricted edge connectivity of graphs,” Discrete Applied Mathematics, 117: 183–193, 2002.

[20] M.Wang and Q. Li, “Conditional edge connectivity properties, reliability comparison and transitivity of graphs,” Discrete Mathematics, 258(1-3): 205–214, 2002.

[21] S. Wang, X. Ma and Y. Ren, “The tightly super 2-good-neighbor connectivity and 2-good-neighbor diagnosability of crossed cubes,” Discrete Applied Mathematics, 70–82, 2017.

[22] S.Y. Wang, J. Yuan and A.X. Liu, “k-Restricted edge connectivity for some interconnection networks,” Applied Mathematics and Computation, 201(1-2): 587–596, 2008.

[23] C.C.Wei and S.Y. Hsieh, “h-restricted connectivity of locally twisted cubes,” Discrete Applied Mathematics, 217: 330–339, 2017.

[24] D.B. West, “Introduction to Graph Theory,” Prentice Hall, NJ, 2 edition, 2001.

[25] J. Wu and G. Guo, “Fault tolerance measures form m-ary n-dimensional hypercubes based on forbidden faulty sets,” IEEE Transactions on Computers, 47(8): 888–893,
1998.

[26] J.M. Xu, “Topological Structure and Analysis of Interconnection Network,” Springer Science & Business Media, 7 edition, 2013.

[27] J.M. Xu, J.W. Wang and W.W. Wang, “On super and restricted connectivity of some interconnection networks,” Ars Combinatoria, 94: 2010.

[28] J.M. Xu and K.L. Xu, “On restricted edge-connectivity of graphs,” Discrete Mathematics, 22: 887–891, 2009.

[29] J.M. Xu, M. Xu and Q. Zhu, “The super connectivity of shuffle-cubes,” Information Processing Letters, 96: 123–127, 2005.

[30] J.M. Xu, Q. Zhu, X.M. Hou and T. Zhou, “On restricted connectivity and extra connectivity
of hypercubes and folded hypercubes,” J. Shanghai Jiaotong Univ. (Sci.), E-10(2): 208–212, 2005.

[31] J.M. Xu, Q. Zhu and M. Xu, “Fault-tolerant analysis of a class of network,” Information Processing Letters, 103(6): 222–226, 2007.

[32] X.Y. Yang, G.M. Megson and D.J. Evans, “Locally twisted cubes are 4-pancyclic,” Applied Mathematics Letters, 17: 919–925, 2004.

[33] W. Yang, H.Z. Li and X.F. Guo, “A kind of conditional fault tolerance of (n, k)-star
graphs,” Information Processing Letters, 110: 1007–1011, 2010.

[34] W. Yang, H. Li and J.X. Meng, “Conditional connectivity of Cayley graphs generated by transposition trees,” Information Processing Letters, 110: 1027–1030, 2010.

[35] J. Yuan, A. Liu, X. Ma, X. Liu, X. Qin and J. Zhang, “The g-good-neighbor conditional diagnosability of k-ary n-cubes under the pmc model and MM* model,” IEEE Transactions on Parallel Distributed Systems, 26(4): 1165–1177, 2015.

[36] Z. Zhang, W. Xiong and W. Yang, “A kind of conditional fault tolerance of alternating
group graphs,” Information Processing Letters, 110: 998–1002, 2010.

[37] Q. Zhu, “On conditional diagnosability and reliability of the BC networks,” Journal of Super computing, 45: 173–184, 2008.