| 研究生: |
黃耀賢 Huang, Yao-Hsien |
|---|---|
| 論文名稱: |
莫氏立方體上的點泛圓性 Node-pancyclicity of Mobius cubes |
| 指導教授: |
謝孫源
Hsieh, Sun-Yuan |
| 學位類別: |
碩士 Master |
| 系所名稱: |
電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年: | 2006 |
| 畢業學年度: | 94 |
| 語文別: | 英文 |
| 論文頁數: | 24 |
| 中文關鍵詞: | 泛圓性 、莫氏立方體 、互連網路 、點泛圓性 |
| 外文關鍵詞: | Mobius cubes, pancyclic, Graph-theoretic interconnection networks, node-pancyclicity, hypercubes |
| 相關次數: | 點閱:159 下載:1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
給定一個圖形,若是這個圖包含所有長度的圓圈(cycle),則我們稱這個圖具有泛圓性(pancyclic)這個性質。接著我們更深入探討點泛圓性問題。我們說一個圖形具有點泛圓性,那就表示對於這圖形上的任何一個點,我們都可以找到所有長度的圓圈,使得點被包含在圓圈裡。而我們已經知道莫氏立方體(Möbius cube)具有泛圓性的性質。在這篇論文中,我們的目的是更進一步證明莫氏立方體具有點泛圓性的性質。
A graph G = (V;E) is said to be pancyclic if it contains cycles of all lengths from 4 to |V| in G. G is called a node-pancyclic graph if, for every node u and any integer l rangeing from 4 to |V|, there exists a cycle C of length l in G such that u is in C. An n-dimensional Mobius cube MQn is a variant of the hypercube. It has been proven that MQn is pan-cyclic. In this paper, we improve this result by showing that MQn is node-pancyclic.
[1] S. G. Akl, Parallel Computation: Models and Methods. Prentice Hall, 1997.
[2] Toru Araki and Yukio Shibata,Pancyclicity of recursive circulant graphs,"Information Processing Letters, vol. 81, pp. 187{190, 2002.
[3] L. Bhuyan and D. P. Agrawal,Generalized hypercubes and hyperbus structure for a computer network," IEEE Transactions on Computers, c. 33, pp. 323{333, 1984.
[4] E. van Blanken, J. van den Heuvel, and H. J. Veldman,Pancyclicity of hamiltonian line graphs,"Discrete Mathematics, vol. 138, issue 1{3, pp. 379{385, 1995.
[5] J. A. Bondy,Pancyclic graphs,"Journal of Combinatorial Theory-Series B, vol. 11, issue 1, pp. 80{84, 1971.
[6] J. C. Bermond, Ed.,Interconnection Networks," a special issue of Discrete Applied Mathematics, vol. 37+38, 1992.
[7] P. Cull, and S. M. Larson,The Mobius cubes," in IEEE Transactions on Computers, vol. 44, no. 5, pp. 647{659, 1995.
[8] Jianxi Fan,Hamiltonian-connectivity and cycle-embedding of the Mobius cubes," Information Processing Letters, vol. 82, pp. 113{117, 2002.
[9] Jianxi Fan, Xiaola Lin, and Xiaohua Jia,Node-pancyclicity and edge-pancyclicity of crossed cubes," Information Processing Letters, vol. 93, pp. 133{138, 2005.
[10] F. Harary, Graph Theory, Addison-wesley, Massachusetts, 1972.
[11] S. Y. Hsieh and C. H. Chen,Pancyclicity on Mobius cubes with maximal edge faults," Parallel Computing, vol. 30, pp. 407{421, 2004. (An preliminary version of this paper appeared in Proceedings of the 7th International Symposium on Parallel Architecture, Algorithms & Networks(ISPAN), pp. 168{173, 2004.)
[12] S. Y. Hsieh, G. H. Chen, and C. W. Ho,Fault-free hamiltonian cycles in faulty arrangement graphs,"IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 3, pp. 223{237, 1999.
[13] D. F. Hsu,Interconnection Networks and Algorithms," a special issue of Networks, vol. 23, no. 4, 1993.
[14] W. Huang, Y. Chuang, J. J. M. Tan, L. Hsu,Fault-free Hamiltonian cycles in faulty Mobius cubes," Computaciony Systemas, vol. 4, no. 2, pp. 106{114, 2000. 23
[15] W. T. Huang, W. K. Chen, and C. H. Chen,Pancyclicity of Mobius cubes", in Proceedings of the 9th International Conference on Parallel and Distributed Systems (ICPADS'02), pp. 591{596, 2002.
[16] Y. C. Tseng, S. H. Chang, and J. P. Sheu,Fault-tolerant ring embedding in star graphs with both link and node failures," IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185{1195, 1997.