擴增立方體(augmented cube)是超立方體(hypercube)的一種變形，其中擁有某些優於超立方體的特性。在這篇論文中，我們研究擴增立方體的邊容錯漢彌爾頓性質(edge-fault-tolerant Hamiltonicity)
。我們將證明在每個節點均連接兩條以上好邊的擴增立方體中，當錯邊個數不超過4n-8，在圖形裡可以找到一條健康(fault-free)的漢彌爾頓圓圈(Hamiltonian cycle)。同時，我們也證明論文中能容忍的錯邊個數是最佳的

The augmented cube is a variation of hypercubes, which possesses some properties superior to the hypercubes. In this thesis, we show that, for any n-dimensional augmented cube (n>=3) with at most 4n-8 faulty edges in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. We also demonstrate that our result is optimal with respect to the number of faulty edges tolerated.

[1] S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, NJ, 1997.
[2] N. Ascheuer, "Hamiltonian path problems in the on-line optimization of flexible manu-facturing systems," Ph.D. Thesis, University of Technology, Berlin, Germany, 1995 (alsoavailable from h ftp://ftp.zib.de/pub/zib- publications/reports/TR-96-03.psi).
[3] L. Bhuyan and D. P. Agrawal, "Generalized hypercubes and hyperbus structure for a
computer network," IEEE Transactions on Computers, 33:323-333, 1984.
[4] C. Chang, T. Sung, and L.Hsu, "Edge congestion and topological properties of crossed
cube," IEEE Transactions Parallel and Distributed Systems, vol. 11, no. 1, pp. 64-80,
2000.
[5] S.A. Choudum, V. Sunitha, Augmented cubes,"Networks," vol. 40(2), pp. 71-84, 2002.
[6] P. Cull, and S. M. Larson, "The Mobius cubes," in IEEE Transactions on Computers,
vol. 44, no. 5, pp. 647-659, 1995.
[7] K. Day and A. E. Al-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Trans-
actions on Parallel and Distributed Systems, vol. 8, no. 9, pp. 903-907, 1997.
[8] K. Diks and A. Pele, "Efficient gossiping by packets in networks with random faults,"
SIAM Journal on Discrete Mathematics, vol. 9, no. 1, pp. 7-18, 1996.
[9] K. Efe, "The crossed cube architecture for parallel computation," IEEE Transactions
on Parallel and Distributed Sytems, vol. 3, no. 5, pp. 513-524, 1992.
[10] A. H. Esfahanian and S. L. Hakimi, "Fault-tolerant routing in de Bruijn communication
networks," IEEE Transactions on Computers, vol. C-34, no. 9, pp. 777-788, 1958.
[11] J. Fan, "Hamitonian-connectivity and cycle-embedding of the Mobius cubes," Informa-
tion Processing Letters, vol. 82, no. 2, pp. 113-117, 2002.
[12] Jung-Sheng Fu, "Cycle embedding in a faulty hypercubes," In Proceeding 9th Interna-
tional Conference Parallel and Distributed Systems, Taiwan, pp. 5-10, 2002.
[13] Jung-Sheng Fu, "Fault-tolerant cycle embedding in the hypercube," Parallel computing,
vol. 29, no. 6, pp. 821-832, 2003.
[14] Jung-Sheng Fu, "Conditional fault-tolerant Hamiltonicity of star graphs," Parallel Com-
puting, accepted. A preliminary version of this paper appeared in the Proceedings of
7th Parallel and Distributed Computing, Applications and Technologies (PDCAT'06),
pp. 11-16, 2006, IEEE Computer Society.
[15] Jung-Sheng Fu, "Conditional fault-tolerant Hamiltonicity of twisted cubes," Proceedings
of 7th Parallel and Distributed Computing, Applications and Technologies (PDCAT'06),
pp. 5-10, 2006, IEEE Computer Society.
[16] H. S. Hung, G. H. Chen, and J. S. Fu, "Conditional fault-tolerant cycle-embedding of
crossed graphs," Proceedings of 7th Parallel and Distributed Computing, Applications
and Technologies (PDCAT'06), pp. 90-95, 2006, IEEE Computer Society.
[17] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, "The twisted
cube," in Proceedings of the Conference on Parallel Architectures and Languages Europe,
Volume I: Parallel Architectures, pages 152-159. Lecture Notes in Computer Science,
1987.
[18] S. Y. Hsieh, C. W. Ho, and G. H. Chen, "Fault-free Hamiltonian cycles in faulty arrange-
ment graphs," IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 3,
pp. 223-237, 1999.
[19] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Longest fault-free paths in star graphs with
vertex faults," Theoretical Computer Science, vol. 262, no. 1-2, pp. 215-227, 2001.
[20] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Longest fault-free paths in star graphs with
edge faults," IEEE Transactions on Computers, vol. 50, no. 9, pp. 960{971, 2001.
[21] S. Y. Hsieh, "Embedding longest fault-free paths onto star graphs with more vertex
faults," Theortical Computer Science, vol. 337, issues 1{3, pp. 370-378, 2005.
[22] S. Y. Hsieh, "Fault-Tolerant cycle embedding in the hypercube with more both faulty
vertices and faulty edges," Parallel Computing, vol. 32, issue 1, pp. 84-91, 2006.
[23] S. Y. Hsieh, and J. Y. Shiu, "Cycle embedding of augmented cubes," Applied Mathe-
matics and Computation, vol. 191, issue 2, pp. 314-319, 2007.
[24] H.C. Hsu, L.C. Chiang, Jimmy J.M. Tan, L.H. Hsu, "Fault hamiltonicity of augmented
cubes," Parallel Computing, vol. 31, pp. 131-145, 2005.
[25] W. Huang, Y. Chuang, J. Tan and L. Hsu, "Fault-free Hamitonian cycle in faulty Mobius
cubes," Journal Computing and Systems, vol.4, pp. 106-114, 2002.
[26] W. Huang, J. Tan, C. Hung, and L. Hsu, "Fault-tolerant Hamitonicity of twisted cubes,"
Journal Parallel and Distributed Computing, vol. 62, no. 4, pp. 591-604, 2002.
[27] W. Huang, Y. Chuang, J. Tan and L. Hsu, "On the fault-tolerant Hamitonicity of faulty
crossed cubes," IEICE Transactions Fundamentals, E85-A, no. 6, pp. 1359-1370, 2002.
[28] W. Huang, W. Chen and C. Chen, "On the fault-tolerant pancyclicity of crossed cubes,"
In Proceeding 9th International Conference Parallel and Distributed Systems, Taiwan,
pp. 591-596, 2002.
[29] H. S. Hung, G. H. Chen, and J. S. Fu, "Fault-free Hamiltonian cycles in crossed cubes
with conditional link faults," Information Sciences, vol. 177, no. 24, pp. 5664-5674, 2007.
[30] S. Lati¯, S. Zheng and N. Bagherzadeh, "Optimal ring embedding in hypercubecubes
with faulty links," In Digest 22nd Symposium Fault-Tolerant Computing, pp. 178-184,
1992.
[31] F. T. Leighton, Introduction to parallel algorithms and architecture: arrays. trees. hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[32] A. C. Liang, S. Bhattacharya, and W. T. Tsai, "Fault-tolerant multicasting on hypercubes," Journal of Parallel and Distributed Computing, vol. 23, pp. 418-428, 1994.
[33] J. H. Park, H. C. Kim, and H. S. Lim, "Fault-Hamiltonicity of hypercube-like interconnection networks," Proceedings of the 19th IEEE International Parallel and Distributed
Processing Symposium, 2005 (IPDPS'05), vol. 1, pp. 60.1, 2005.
[34] N. Singhvi and K. Ghose, "The Mcube: a symmetrical cube based network with twisted
links," Proceedings of the 9th International Symposium of Parallel Processing, Honolulu,
pp. 11-16, 1995.
[35] C. H. Tsai, "Linear array and ring embeddings in conditional faulty hypercubes," Theoretical Computer Science, vol. 314, pp. 431-443, 2004.
[36] Y. C. Tseng, "An efficient scheme for embedding a ring into an injured hypercube with
both faulty links and faulty nodes," In Proceeding 3rd International Conference High
Performance Computing, pp. 165-169, 1996.
[37] Y. C. Tseng, "Resilient and flexible ring embedding in an injured hypercube," Journal
Information Science and Engineering, vol. 12, no. 4, pp. 567-583, 1996.
[38] Y. C. Tseng, S. H. Chang, and J. P. Sheu, "Fault-tolerant ring embedding in a star
graph with both link and node failures," IEEE Transactions on Parallel and Distributed
Systems, vol. 8, no. 12, pp. 1185-1195, 1997.
[39] N. C. Wang, C. P. Chu, and T. S. Chen, "A dual-Hamiltonian-path-based multicasting
strategy for wormhole-routed star graph interconnection networks," Journal of Parallel
and Distributed Computing, vol. 62, issue 12, pp. 1747-1762, 2002.
[40] N. C. Wang, C. P. Yen, and C. P. Chu, "Multicast communication in wormhole-routed
symmetric networks with Hamiltonian cycle model," Journal of Systems Architecture,
vol. 51, issue 3, pp. 165-183, 2005.
[41] J. Wu, "Safety levels - an e±cient mechanism for achieving reliable broadcasting in
hypercubes," IEEE Transactions on Computers, vol. 44, no. 5, pp. 702-706, 1995.
[42] P. J. Yang, S. B. Tien, and C. S. Raghavendra, "Embedding of rings and meshes onto
faulty hypercubes using free dimensions," IEEE Transactions on Computers, vol. 43,
no. 5, pp. 608-613, 1994.
[43] 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.