近年來，由於計算機VLSI技術的快速發展，一個多處理器系統可能包含成千上百個處理器。研究一個互聯網路的錯誤容忍度是確保系統安全性的重要步驟。更進一步的，一個系統如有能力自動對處理器偵錯，才能將壞的處理器進行替換。

超邊連通度是評估一個大型互聯網路安全性及錯誤容忍度的重要參數。給一個非負整數g，一個圖G的g-超邊連通度代表的意義是拿掉最少的邊數，使得圖G不連通，但是剩下的圖，每個部分都至少有g個點。本篇論文證明了n維超立方體的g-超邊連通度是4n－8。

目前偵錯問題一經廣泛的被討論，很多有名的互聯網路系統之偵錯度也已經被計算出來。本篇論文提供了決定系統強偵錯度及條件偵錯度的充分條件。我們運用它證明了增廣立方體的強偵錯度是2n－1，條件式偵錯度是6n－17。

Due to the rapid development of VLSI technology in recent years, a multiprocessor system may contains hundreds or even thousands of processors. Studying the fault tolerance of interconnection networks is an important step in ensuring system reliability. Furthermore, the system should have the ability to distinguish between faulty vertices and fault-free ones. Then, faulty vertices can be replaced by additional fault-free ones.
Extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Given a graph G and a non-negative
integer g, the g-extra edge connectivity of G is the minimum cardinality of an edge subset in G, if it exists, whose deletion disconnects G and causes every remaining component to have more than g vertices. This dissertation shows that the 3-extra edge connectivity of an n-dimensional hypercube-like network is 4n − 8 for n ≥ 6.
The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. In this dissertation, some useful sufficient
conditions are proposed to determine strong diagnosability and the conditional diagnosability of a system. We then apply them to show that an n-dimensional augmented cube
AQn is strongly (2n−1)-diagnosable for n ≥ 5 and the conditional diagnosability of AQn is 6n− 17 for n ≥ 6. Our result demonstrates that the conditional diagnosability of AQn is about three times larger than the classical diagnosability.

[1] T. Araki and Y. Shibata, “Diagnosability of networks represented by the Cartesian
product”, IEICE Transactions on Fundamentals, vol. E83-A, no. 3, pp. 465–470,
2000.
[2] J. R. Armstrong and F. G. Gray, “Fault diagnosis in a boolean n cube array of
multiprocessors,” IEEE Transactions on Computers, vol. 30, no. 8, pp. 587–590,
1981.
[3] M. O. Ball,“Complexity of network reliability computation,” Networks, vol. 10, pp.
153–165, 1980.
[4] F. T. Boesch, “Graph theory and reliable network synthesis, Technical Report, Electrical
Engineering and Computer Science Department, Stevens Institute Technology,
1986.
[5] W. G. Bouricius, W. C. Carter, D. C. Jessep, P. R. Schneider and A. B. Wadia,
“Reliability modeling for fault tolerant computers,” IEEE Transations on Computers,
vol. C-20, pp. 1306–1311, 1971.
[6] M. Chan, “The distinguishing number of the augmented cube and hypercube powers,”
Discrete Mathematics, vol. 308, no. 11, pp. 2330–2336, 2008.
[7] N. W. Chang, S. Y. Hsieh “Conditional diagnosability of augmented cubes under the
PMC model,” IEEE Transactions on Dependable and Secure Computing, vol. 9, no.
1, pp. 46–60, 2012.
[8] F. B. Chedid, “On the generalized twisted cube,” Information Processing Letters,
vol. 55, no. 1, pp. 49–52, 1995.
[9] E. Cheng and L. Liptak, “A kind of conditional vertex connectivity of Cayley graphs
generated by transposition trees,” Congressus Numerantium, vol. 199 pp. 167–173,
2009.
[10] P. Cull and S.M. Larson, “The M¨obius cubes,” IEEE Transactions on Computers,
vol. 44, no. 5, pp. 647–659, 1995.
[11] N. W. Chang, S. Y. Hsieh “ (2,3)-Extraconnectivities of hypercube-like networks,”
Journal of Computer and System Sciences, vol. 79, no. 5, pp. 669–688, 2013.
[12] G. Y. Chang, G. J. Chang, and G. H. Chen, “Diagnosabilities of regular networks,”
IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 314–323,
2005.
[13] S. A. Choudum, V. Sunitha, “Augmented cubes,” Networks, vol. 40, no. 2, pp. 71–84,
2002.
[14] P. Dundar, “Augmented cubes and its connectivity numbers,” Neural Network World,
vol. 15, no. 1, pp. 1–8, 2005.
[15] K. Efe, “The crossed cube architecture for parallel computation,” IEEE Transaction
on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513–524, 1992.
[16] J. F`abrega and M. A. Fiol, “Extraconnectivity of graphs with large girth,” Discrete
Mathematics, vol. 127, pp. 163–170, 1994.
[17] J. F`abrega and M. A. Fiol, “On the extraconnectivity of graphs ,” Discrete Mathematics,
vol. 155, pp. 49–57, 1996.
[18] J. X. Fan and L. Q. He, “BC interconnection networks and their properties,” Chinese
Journal of Computers, vol. 26, no. 1, pp. 1–7, 2003.
[19] J. Fan, “Diagnosability of crossed cubes under the two strategies,” Chinese Journal
of Computers, vol. 21, no. 5, pp. 456–462, 1998.
[20] J. Fan, “Diagnosability of the M¨obius cubes,” IEEE Transactions on Parallel and
Distributed Systems, vol. 9, no. 9, pp. 923–928, 1998.
[21] A. D. Friedman and L. Simoncini, “System-level fault diagnosis,” The Computer
Journal, vol. 13, no. 3, pp. 47-53, 1980.
[22] H. Fugiwara and K. Kinoshita, “On the computational complexity of system diagnosis,”
IEEE Transactions on Computers, vol. 27, no. 10, pp. 881–885, 1978.
[23] A. Ghafoor, “A class of fault-tolerant multiprocessor networks,” IEEE Transactions
on Reliability, vol. 38, no. 1, pp. 5–15, 1989.
[24] A. Ghafoor, “Partitioning of even networks for improved diagnosability,” IEEE
Transactions on Reliability, vol. 39, no. 3, pp. 281–286, 1990.
[25] F. Harary, “Conditional connectivity,” Networks, vol. 13, no. 3, pp. 347–357, 1983.
[26] H. Heffes and A. Kumar, “Incorporating dependent node damage in deterministic
connectivity analysis and synthesis of networks,” Networks, vol. 16, pp. 51–65, 1986.
[27] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, “The twisted
cube,” Parallel Architectures and Languages Europe, pp. 152–159, 1987.
[28] S. L. Hakimi and A. T. Amin, “Characterization of connection assignment of diagnosable
systems,” IEEE Transactions on Computers, vol. 23, pp. 86–88, 1974.
[29] S. Y. Hsieh and J. Y. Shiu, “Cycle embedding of augmented cubes,” Applied Mathematics
and Computation, vol. 191, no. 2, pp. 314–319, 2007.
[30] S. Y. Hsieh and Y. S. Chen, “Strongly diagnosable product networks under the
comparison diagnosis model,” IEEE Transactions on Computers, vol. 57, no. 6, pp.
721–732, 2008.
[31] S. Y. Hsieh and Y. S. Chen, “Strongly diagnosable systems under the comparison
diagnosis model,” IEEE Transactions on Computers, vol. 57, no. 12, pp. 1720–1725,
2008.
[32] G. H. Hsu, C. F. Chiang, L. M. Shih, L. H. Hsu, and J. J. M. Tan, “Conditional diagnosability
of hypercubes under the comparison diagnosis model,” Journal of Systems
Architecture, vol. 55, no. 2, pp. 140–146, 2009.
[33] 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.
[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, no. 2, pp. 246-255, 2011.
[35] Y. Ishida, N. Adachi, and H. Tokumaru, “Diagnosability and distinguishability analysis
and its applications,” IEEE Transactions on Reliability, vol. 36, no. 5, pp. 531–538,
1987.
[36] A. Kavianpour, “Sequential diagnosability of star graphs,” Computers and Electrical
Engineering, vol. 22, no. 1, pp. 37–44, 1996.
[37] A. Kavianpour and K. H. Kim, “Diagnosability of hypercubes under the pessimistic
one-step diagnosis strategy,” IEEE Transactions on Computers, vol. 40, no. 2, pp.
232–237, 1991.
[38] A. Kavianpour and K. H. Kim, “A comparative evaluation of four basic system-level
diagnosis strategies for hypercubes,” IEEE Transactions on Reliability, vol. 41, no.
1, pp. 26–37, 1992.
[39] P. L. Lai, J. J. M. Tan, C. P. Chang, and L. H. Hsu, “Conditional diagnosability
measures for large multiprocessor systems,” IEEE Transactions on Computers, vol.
54, no. 2, pp. 165–175, 2005.
[40] 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.
[41] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Lipt´ak, “Conditional diagnosability
of Cayley graphs generated by transposition trees,” Journal of Interconnection
Networks, vol. 9, no. 1-2, pp. 83–97, 2008.
[42] M. L¨u, G. L. Chen, C. Lv, “On super connectivity of Cartesian product graphs,”
Networks, vol. 52, no.2, pp. 78–87, 2008.
[43] M. L¨u, G. L. Chen, and X. R. Xu, “On super edge-connectivity of product graphs,”
Applied Mathematics and Computation, vol. 207, no. 2, pp. 300–306, 2009.
[44] M. J. Ma, G. Z. Liu, and J. M. Xu, “The super connectivity of augmented cubes,”
Information Processing Letters, vol. 106, no. 2, pp. 59–63, 2008.
[45] M. Ma, G. Liu, and J. M. Xu, “Panconnectivity and edge-fault-tolerant pancyclicity
of augmented cubes,” Parallel Computing, vol. 33, no. 1, pp. 36–42, 2007.
[46] 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.
[47] 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.
[48] J. H. Park and K. Y. Chwa, “Recursive circulant: a new topology for multicomputer
networks,” in Proceedings of International Symposium on Parallel Architectures, Algorithms
and Networks, pp. 73–80, 1994.
[49] J. H. Park and K. Y. Chwa, “Recursive circulants and their embeddings among
hypercubes,” Theoretical Computer Science vol. 244, no. 1-2, pp. 35–62, 2000.
[50] C. D. Park and K. Y. Chwa,“Hamiltonian properities on the class of hypercube-like
networks,” Information Processing Letters, vol. 91, no. 1, pp. 11–17, 2004.
[51] Y. Pan, “Fault tolerance in the block-shift network,” IEEE Transactions on Reliability,
vol. 50, no. 1, pp. 85–91, 2001.
[52] F. P. Preparata, G. Metze, and R.T. Chien, “On the connection assignment problem
of diagnosis systems,” IEEE Transactions on Electronic Computers, vol. 16, no. 12,
pp. 848–854, 1967.
[53] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions
on Computers, vol. 37, no. 7, pp. 867–872, 1988.
[54] A. Sengupta and A. Dahbura, “On self-diagnosable multiprocessor systems: diagnosis
by the comparison approach,” IEEE Transactions on Computers, vol. 41, no. 11, pp.
1386–1396, 1992.
[55] N. K. Singhvi and K. Ghose, “The Mcube: a symmetrical cube based network with
twisted links,” in Proceedings of the 9th IEEE International Parallel Processing Symposium
IPPS 1995, pp. 11–16, 1995.
[56] A. K. Somani, V. K. Agarwal, and D. Avis, “A generalized theory for system level
diagnosis,” IEEE Transactions on Computers, vol. 36, no. 5, pp. 538–546, 1987.
[57] A. S. Vaidya, P.S. N. Rao, and S. R. Shankar, “A class of hypercube-like networks,”
in Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing,
pp. 800–803, 1993.
[58] M. Wan and Z. Zhang, “A kind of conditional vertex connectivity of star graphs,”
Applied Mathematics Letters, vol. 22, no. 2, pp. 264–267, 2009.
[59] S. Y. Wang, J. Yuan, and A. X. Liu, “k-restricted edge connectivity for some interconnection
networks,” Applied Mathematics and Computation, vol. 201, no. 1-2, pp.
587–596, 2008.
[60] D. Wang, “Diagnosability of enhanced hypercubes,” IEEE Transactions on Computers,
vol. 43, no. 9, pp. 1054–1061, 1994.
[61] D. Wang, “Diagnosability of hypercubes and enhanced hypercubes under the comparison
diagnosis model,” IEEE Transactions on Computers, vol. 48, no. 12, pp.
1369–1374, 1999.
[62] W. W. Wang, M. J. Ma, and J. M. Xu, “Fault-tolerant pancyclicity of augmented
cubes,” Information Processing Letters, vol. 103, no. 2, pp. 52–56, 2007.
[63] D. B. West, Introduction to Graph Theory, Prentice Hall Publishers, 2001.
[64] M. Xu and J. M. Xu, “The forwarding indices of augmented cubes,” Information
Processing Letters, vol. 101, no. 5, pp. 158–159, 2007.
[65] J. M. Xu, Topological structure and analysis of interconnection networks, Kluwer
Academic Publishers, 2001.
[66] J. M. Xu, M. L¨u, M. J. Ma, and A. Hellwig, “Super connectivity of line graphs,”
Information Processing Letters, vol. 94, no. 4, pp. 191–195, 2005.
[67] J. M. Xu, M. Xu, Q. Zhu,“The super connectivity of shuffle-cubes,” Information
Processing Letters vol. 96 pp.123–127, 2005.
[68] J. M. Xu, J. W. Wang, and W. W. Wang, “On super and restricted connectivity of
some interconnection networks,” Ars Combinatoria, 2006.
[69] J. M. Xu, Q. Zhu, and M. Xu, “Fault-tolerant analysis of a class of networks,”
Information Processing Letters, vol. 103, no. 6, pp. 222–226, 2007.
[70] X. F. Yang, D. J. Evans, and G. M. Megson, “The locally twisted cubes,” International
Journal of Computer Mathematics, vol. 82, no. 4, pp. 401–413, 2005.
[71] W. H. Yang and J. X. Meng, “Extraconnectivity of hypercubes,” Applied Mathematics
Letters, vol. 22, no. 6, pp. 887–891, 2009.
[72] W. Yang, H. Li, J. X. Meng, “Conditional connectivity of Cayley graphs generated by
transposition trees,” Information Processing Letters, vol. 110 pp. 1027–1030, 2010.
[73] J. Zhao, F. J. Meyer, N. Park, and F. Lombardi, “Sequential diagnosis of processor
array systems,” IEEE Transactions on Reliability, vol. 53, no. 4, pp. 487–498, 2004.
[74] 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.
[75] Q. Zhu, “On conditional diagnosability and reliability of the BC networks,” The
Journal of Supercomputing, vol. 45, no. 2, pp. 173–184, 2008.
[76] Q. Zhu, J. M. Xu, X. M. Hou, and M. Xu, “On reliability of the folded hypercubes,”
Information Sciences, vol. 177, no. 8, pp. 1782–1788, 2007.
[77] Q. Zhu, “On conditional diagnosability and reliability of the BC networks,” The
Journal of Supercomputing, vol. 45, no. 2, pp. 173–184, 2008.
[78] Q. Zhu, S. Y. Liu, and M. Xu, “On conditional diagnosability of the folded hypercubes,”
Information Sciences, vol. 178, no. 4, pp. 1069–1077, 2008.