低維度Cayley圖之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：143

、訪客IP：3.144.4.54

姓名

林容新(Rong-Shin Lin) 查詢紙本館藏

畢業系所

數學系

論文名稱

低維度Cayley圖之研究
(On Cayley graphs of degree 3)

相關論文

★ n 階置換Cayley 圖之研究	★ 超立方體與其變形的覆蓋容器
★ 路徑與圈嵌入有缺損的超立方體	★ 樹圖最大特徵值的討論
★ On the Spectrum of Trees

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在[3]中，Dirac在1952年證明，只要簡單圖G中，頂點個數至少3個，頂點的維度都大於或等於頂點個數的一半，就有漢米頓圈。Chvátal-Erdös在1972年證明，簡單圖G中，頂點個數至少3個且κ(G)大於或等於 α(G)，則有漢米頓圈。此兩類的圖，邊的個數都要相當多，而在邊數比較少的圖中是否有漢米頓圈則是一個難解的問題。例如：Odd graph O(n)，頂點集合V為2n-1個元素集合的n-1元子集合，任二頂點A與B相鄰若且唯若A交集 B為空集合。這種圖有個頂點，但每點的邊數只有n條。這種圖是否是漢米頓圖就是很難的問題，n=3是Petersen圖，沒有漢米頓圈，但n大於或等於 4時是有名的Kneser 猜想：假設n>3，則O(n) 是漢米頓圖。這個問題大部分的情況到現在仍未解決。
考慮最極端的例子，我們想要檢查一些3-正則圖是否有漢米頓圈。根據Cayley圖是漢米頓圖的猜想，我們有興趣去知道3-正則Cayley圖是否有漢米頓圈。然而要去分析所有的3-正則Cayley圖是一件難事，特別是缺乏邊對稱的圖[8]。本論文將探討下列特殊的3-正則類：1.圈化圖(Cycle connected graph)。2.SEP(n)。

摘要(英)

We wnat to check some 3-regular graphs has Hamiltonian cycle.According to the conjucture:Cayley graphs are Hamiltonian cycle,we want to know 3-regular Cayley graphs has Hamiltonian cycle.But it is hard to anlysis all 3-regular Cayley graphs.In this paper,we discuss some specal 3-regular graphs: Cycle connected graph and SEP(n).

關鍵字(中)

★ 漢米頓圈
★ Cayley 圖

關鍵字(英)

★ Cayley graph
★ Hamiltonian cycle

論文目次

圖形的目錄 ……………二
前言 ………………………………………………… 1
第一章基本定義 …………………………………… 2
第二章 Cayley 圖及圈化圖 …………… 4
第三章漢米頓圈的問題 …………………… 13
第四章 K-覆蓋連通 …………………………… 19
第五章討論 ……………………………………… 22
參考文獻 …………………………………………… 23

參考文獻

[1] Bette Bultena and Frank Ruskey,“Transition Restricted Gray Codes”, the Electronic Journal of Combinatorics:Volume 3,Paper R11.March 14,1996
[2] Chang-Hsing Tsai, Jimmy J. M. Tan, Tyne Liang, and Lih-Hsing Hsu,” Fault – Tolerant Hamiltonian Laceablility of Hypercubes,”preprint.
[3] Douglas B. West, “Introduction to Graph Theory” Second edition: Prentice Hall 2001
[4] Friedhelm Meyer auf der Heide and Berthold VÖcking ,” Short paths routing in arbitrary networks”, Journal of Algorithms, Vol. 31, No. 1, pp. 105-131, 1999.
[5] G. A. Miller, Blichfeldt and Dickson ,” Theory and Applications of Finite Groups “, John Wiley and sons,Inc.,1916,reprinted Dover 1961
[6] G.Simmons,”Almost all n-dimensional rectangular lattices are Hamiltonian laceable”,Congressus Numerantium 21,1978,pp.103-108.
[7] Harry Dweighter,” Problem E2569”,American Mathematical Monthly,82 (1975) 1010.
[8] H.S.M. Coxeter, “Zero-Symmetric Graphs Trivalent Graphical Regular Representations of Groups.” Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London (1981)
[9] K. Menger, “Zur allgemeinen Kurventheroie”, Fund. Math., 10, 1927, 95-115
[10] Leighton,F.T., “Introduction to Parallel Algorithms and Architectures : Arrays,Trees,Hypercubes.” ,Morgan Kaufmann Publishers, Inc.,(1992)
[11] Marie-Claude Heydemann and Bertrand Ducourthial, “Cayley Graphs And Interconnection Networks” in Graph Symmetry, Algebraic Methods and Applications, "NATO ASI C", vol. 497 , p 167-226, 1997.
[12] Michael Albert, R. E. L. Aldred and Derek Holton,”On 3*-connected graphs”preprint.
[13] S.B. Akers and B. Krishnamurthy, “A Group Theoretic Model for Symmetric Interconnection Networks”, IEEE Transaction on Computer, Vol. c-38, No. 4, April 1989, pp. 555-566
[14] Shahram. Latifi,Pradip K,Srimani,”SEP:A Fixed Degree Regular Network for Msaaively Parallel Systems.” preprint.
[15] Shahram Latifi and Pradip Srimani,” A New Fixed Degree Regular Network for Parallel Processing,” Proceedings of Eighth IEEE Symposium on Parallel and Distributed Processing, October 1996.
[16] Preparata, F. P. and Vuillemin, J. : “The Cube-Connected Cycle : A Versatile
Network for Parallel Computation.” Communication of ACM Vol.24 No5,1987,p300-309
[17] 林政寬,n階置換Cayley圖之研究, 中央大學數學研究所碩士論文,preprint.
[18] 徐嘉陽, 特殊Cayley 圖的寬距, 中央大學數學研究所碩士論文(1994)
[19] 雷偉明, Cayley 圖的直徑與寬直徑的研究, 中央大學數學研究所碩士論文(1996) 23

指導教授

黃華民(Hua-Min Huang)

審核日期

2002-7-19

推文