簡易檢索 / 詳目顯示

研究生: 黃耀賢
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 Introduction                 4 1.1 Motivation and Related Discussion    4 1.2 Preview of This Thesis          5 2 Preliminaries                 7 2.1 Basic Defnitions of Graph        7 2.2 The Defnitions of Mobius cube      8 3 Node-pancyclicity of Mobius cubes     12 4 Concluding Remarks             22

    [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.

    下載圖示 校內:2009-06-30公開
    校外:2009-06-30公開
    QR CODE