臺灣博碩士論文加值系統

星狀圖是超立方體之外的另一種頗具吸引力的網路結構。這篇論文中，我們研究探討n 階層之星狀圖上之漢米爾頓性質。我們證明在n(n>=4)階層之星狀圖中包含至多3n-10 條錯誤邊且任一點至少連接兩條非錯誤邊之情形下，則此星狀圖必存在一條漢米爾頓迴圈。我們的結論改進了前人最佳結果為容錯2n-7 條錯誤邊。我們提出一最差情況，在由六個節點形成之迴圈上每隔一個節點連接n-3 條錯誤邊。此情況說明我們的結果為最佳。

The star graph is viewed as an attractive alternative to the hypercube. In this paper, we investigate the hamiltoncity of an n-dimensional star graph. We show that, for any n-dimensional star graph (n >= 4) with at most 3n-10 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves on the previously best known result for the case where the number of tolerable faulty edges is bounded by 2n-7. We also demonstrate that our
result is optimal with respect to the worst case scenario, where every other node of a six-node cycle is incident to exactly n-3 faulty non-cycle edges.

Abstrct(in Chinese) i
Abstrct(in English) ii
Acknowledge iii
Contents v
List of Figures vii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Preview of This Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Preliminaries 4
2.1 De‾nition of Star Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Some Properties of Star Graph . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Two Special Cases 12
3.1 Fault-Tolerant Hamiltonicity of Faulty S4 . . . . . . . . . . . . . . . . . .12
3.2 Fault-Tolerant Hamiltonicity of Faulty S5 . . . . . . . . . . . . . . . . . .12
4 The General Case 20
4.1 Some New Properties of Star Graph . . . . . . . . . . . . . . . . . . . . . .20
4.2 The Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Conclusion 31

[1] S. B. Akers, D. Horel, and B. Krishnamurthy, "The star graph: an attractive alternative to the n-cube," Proceedings of the International Conference on Parallel Processing, 1987, pp.393-400.
[2] S. B. Akers and B. Krishnamurthy, "A group-theoretic model for symmetric interconnection networks," IEEE Transactions on Computers, vol. 38, no. 4, pp. 555-566, 1989.
[3] S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, NJ, 1997.
[4] N. Ascheuer, "Hamiltonian path problems in the on-line optimization of °exible manufacturing 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).
[5] N. Bagherzadeh, N. Nassif, and S. Lati‾, "A routing and broadcasting scheme on faulty star graphs," IEEE Transactions on Computers, vol. 42, no. 11, pp. 1398-1403, 1993.
[6] J. C. Bermond (Ed.), "Interconnection networks," Discrete Applied Mathematics, vol.37+38, 1992 (special issue).
[7] L. Bhuyan and D. P. Agrawal, "Generalized hypercube and hyperbus structures for a computer network," IEEE Transactions on Computers, vol. C-33, pp. 323-333, 1984.
[8] K. Day and A. R. Tripathi, "A comparative study of topological properties of hypercubes and star graphs," IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 1, pp. 31-38, 1994.
[9] P. Fragopoulou and S. G. Akl, "Optimal communication algorithms on star graphs using spanning tree constructions," Journal of Parallel and Distributed Computing, vol. 24, no. 1, pp. 55-71, 1995.
[10] Jung-Sheng Fu, "Conditional fault-tolerant Hamiltonicity of star graphs," Parallel Computing, accepted. A preliminary version of this thesis appeared in the Proceedings of 7th Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), pp. 11-16, 2006, IEEE Computer Society.
[11] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Hamiltonian laceability of star graphs,"Networks, vol. 36, no. 4, pp. 225-232, 2000.
[12] 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, issues 1-2, pp. 215-227, 2001.
[13] 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.
[14] 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.
[15] S. Y. Hsieh, C. D. Wu. "The veried program of fault-free Hamiltonian cycles in Star graph with conditional edge faults" http://algorithm.csie.ncku.edu.tw/»basicios.
[16] D. F. Hsu, "Interconnection networks and algorithms," Networks, vol. 23, no. 4, 1993 (special issue).
[17] J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall, "Embedding of cycles and grids in star graphs,"Journal of Circuits, Systems, and Computers, vol. 1, no. 1, pp. 43-74, 1991.
[18] F. T. Leighton, Introduction to parallel algorithms and architecture: arrays¢ trees¢ hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[19] Tseng-Kuei Li, "Cycle embedding in star graphs with edge faults," Applied Mathematics and Computation, vol. 167, no. 2, pp. 891-900, 2005.
[20] V. E. Mendia and D. Sarkar, "Optimal broadcasting on the star graph," IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 4, pp. 389-396, 1992.
[21] Z. Miller, D. Pritikin, and I. H. Sudborough, "Near embeddings of hyperucbes into Cayley graphs on the symmetrical group," IEEE Transactions on Computers, vol. 43,
no. 1, pp. 13-22, 1994.
[22] S. Ranka, J. C. Wang, and N. Yeh, "Embedding meshes on the star graph," Journal of Parallel and Distributed Computing, vol. 19, pp. 131-135, 1993.
[23] K. Qiu, S. G. Akl, and H. Meijer, "On some properties and algorithms for the star and pancake interconnection networks," Journal of Parallel and Distributed Computing. vol. 22, no. 1, pp. 418-428, 1994.
[24] P. Y. Tsai, J. S. Fu, and G. H. Chen, "Hamiltonian-laceability in star graphs with conditional edge faults," proceedings of the International Computer Symposium, vol. 1,
Taipei, Taiwan, pp. 144-152, 2006.
[25] P. Y. Tsai, J. S. Fu, and G. H. Chen, "Fault-Free Longest Paths in Star Networks with Conditional Link Faults," Theoretical Computer Science, submitted.
[26] 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.
[27] 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.
[28] 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.