以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：11

、訪客IP：3.145.68.101

姓名	孫召明(Chao-Ming Sun)  查詢紙本館藏	畢業系所	數學系
論文名稱	路徑與圈嵌入有缺損的超立方體 (Path and Cycle Embedding in Faulty Hypercubes)
相關論文	★ n 階置換Cayley 圖之研究 ★ 低維度Cayley圖之研究 ★ 超立方體與其變形的覆蓋容器 ★ 樹圖最大特徵值的討論 ★ On the Spectrum of Trees
檔案	[Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載] 本電子論文使用權限為同意立即開放。 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中)	一個連接網路的結構通常可以用一個圖來表示。可是在連接網路的拓樸與設計上存在許多相互抵觸的要求。要設計一個完美的網路符合各方面的要求而且都是最佳化的狀況是幾乎不可能的事。超立方體(hypercube)網路是一個最受歡迎的拓樸結構之一。因為它有很多好的性質已經廣泛被使用，例如：規則的(regular)，對稱性的(symmetric)，強大的連接性和相關最小直徑[47,63]等等。在1976年，Hayes是第一篇文獻直接討論關於漢米爾頓的(Hamiltonian)和容錯的性質。從那時候開始對於漢米爾頓性質與容錯性質的文章就不斷越來越多。很多組合，代數學，和其他數學結構是與漢米爾頓性質與容錯性質有關係。因此，產生很多有意思的問題與重要的結果。例如：Hayes[37]，Simmons [65]，Lewinter和Widulski[45]等等都是在這方面很棒的文章。 容錯漢米爾頓存在著各式各樣的問題，例如: 圈(cycle)或路徑(path)嵌入在缺損連接網路問題。但是，在二分圖裡的路徑顏色是相互交錯的。所以，對於圖總點數大於3時，任何二分圖都不是漢米爾頓連通(hamiltonian connected)。因此，Simmon [65]定義漢米爾頓連結性的觀念。在給定一個二分圖中，去探討嵌入各式各樣的圈或路徑是一個重要的課題。圈或路徑嵌入問題就是漢米爾頓的問題的推廣。 在本篇論文裡有4章。我們將研究可否將路徑和圈嵌入有缺損的超立方體圖裡。在第1章，我們提及一些基本的定義和在漢米爾頓問題上古典結果。在第2章，我們在某一些缺損超立方體圖上討論漢米爾頓相關問題。在第3章，我們在某一些缺損超立方體圖上討論任意長度的圈和路徑嵌入問題。在第4章，我們提議並且討論︰在超立方體圖裡討論彼此相互獨立的漢米爾頓路徑和圈的問題。在最後，我們將對於這篇論文的結果與未來工作做一個總結並討論未來可能進行研究的方向。
摘要(英)	The architecture of an interconnection network is usually represented by a graph. There exist mutually conflicting requirements in designing and topology of interco- nnection networks. It became almost impossible for us to design a network which is optimum in all aspects. The hypercube network is one of the most popular topologies among the interconnection networks. It has widely used due to many of its attractive properties, including regular, symmetric, strong connectivity and relative small diameter [48, 64] etc. The first paper dealing directly with hamiltonian property and fault- tolerant property appeared in 1976 Hayes [38]. Since that time the interest in hamiltonian property and fault-tolerant property has been on increase. Many combinatorial, algebraic, and other mathematical structures are linked to hamiltonian property and fault-tolerant property. There are lots of intriguing problems and significant results. Excellent surveys of them are provided by Hayes [38], Simmons [66], Lewinter and Widulski [46] etc. There are various fault-tolerant hamiltonian problems, such as cycle (path) embedding problems in hamiltonian faulty interconnection networks. However, any bipartite graph G is not hamiltonian connected for V(G). Any hamiltonian bipartite graph G = (V0; V1;E) satisfies |V0| = |V1|. Simmons [66] introduced the concept of hamiltonian laceability for hamiltonian bipartite graph. Hsieh et al. [41] introduced the concept of strongly hamiltonian laceability. Lewinter and Widulski [46] further introduced the concept of hyper-hamiltonian laceability. The Hamiltonian laceability, which deals with embedding a hamiltonian path in a given bipartite graph, is an important topic in interconnection networks. The cycle (path) embedding problem is a derivation of hamiltonian problems. In this thesis, there are four chapters in this thesis. We’’ll study the path and cycle embedding in faulty hypercubes. In Chapter 1, we mention some basic definitions and classical results on hamiltonian problem. In Chapter 2, we discuss hamiltonian problems on some faulty hypercubes. In Chapter 3, we discuss the cycle and path embeddingproblem, which deals with all the possible lengths of cycle and path in faulty hypercubes under some conditions. In Chapter 4, we propose and discuss related problems: Mutually independent hamiltonian paths and cycles problems in hypercubes. In the final section, we give our concluding remarks.
關鍵字(中)	★ 偶泛圈 ★ 偶泛連通 ★ 缺損的超立方體 ★ 漢米爾頓路徑 ★ 漢米爾頓 ★ 容錯	關鍵字(英)	★ hamiltonian laceable ★ fault-tolerant ★ faulty hypercube ★ bipanconnected ★ bipancyclic ★ hamiltonian
論文目次	摘要………………………………………………………………………………i 目錄………………………………………………………………………………vi 圖目錄……………………………………………………………………………viii 1 Basic definitions and some classical results on hamiltonian problem . . . . . . . . . 1 1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Some classical results on the hamiltonian problem . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Some classical results on the hamiltonian connectivity problem . . . . . . . . . . . . 16 2 Hamiltonian laceability of faulty hypercubes . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Basic properties of the hypercubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.1 Fault-tolerant hamiltonian laceability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.2 Fault-tolerant hamiltonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3 Bipanconnectivity and bipancyclitity of faulty hypercubes . . . . . . . . . . . . . . . . . 56 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.2.1 Shorter proof on some known results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.2.2 Fault-tolerant bipanconnectivity and edge-bipancyclicity . . . . . . . . . . . . . . . 63 3.2.3 Fault-tolerant vertex-bipancyclicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4 Mutually independent hamiltonian paths and cycles in hypercubes . . . . . . . . . . . 81 4.1 Some useful notation and lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2 Mutually independent hamiltonian cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3 Mutually independent hamiltonian paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5 Conclusion and discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
參考文獻	[1] D. Amar, I. Fournier, and A. Germa, ``Pancyclism in Chv¶atal-Erd}os graphs," Graphs Combinat., Vol. 7, pp. 101-112, 1991. [2] B. Alspach, ``Hamiltonian cycles in vertex-transitive graphs of order 2p," Second International Conference on Combinat. Math., pp. 131-139, 1978. [3] B. Alspach, and D. Hare, ``Edge-pancyclic block-intersection graphs," Discrete Math., Vol. 97, pp. 17-24, 1979. [4] L. Babai, Problem 17, unsolved problems, Summer Research Workshop in Algebraic Combinatorics, Simon Fraser University, July 1979. [5] K. S. Bagga and B. Varma, Bipartite graphs and degree conditions," in: Graph Theory, Combinatorics, Algorithms and Applications, Proc. 2nd Int. Conf. san Francisco,CA, 1989, 1991, pp. 564-573. [6] J. S. Bagga, and B. N. Varma, ``Hamiltonian properties in bipartite graphs," Syst. Sci. and Math. Sci. , Vol. 26, pp. 71-85, 1999. [7] D. Bauer, H. J. Broersma, H. J. Veldman, and L. Rao, ``A generalization of a result of HÄaggkvist and Nicoghossian," J. Combinat. Theory B, Vol. 47, pp. 237-243, 1989. [8] D. Bauer, A. Morgana, E. Schmeichel, and H. J. Veldman, ``Long cycles in graphs with large degree sums," Discrete Math., Vol. 79, pp. 59-70, 1990. [9] D. Bauer, H. J. Broersma, and H. J. Veldman, ``Not every 2-tough graph is Hamiltonian," Discrete Appl. Math., Vol. 99, pp. 317-321, 2000. [10] J. A. Bondy, ``Longest paths and cycles in graphs of high degree," Research Report CORR 80{16, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, 1980. [11] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York, 1980. [12] J. A. Bondy, ``Pancyclic graphs I," J. Combinat. Theory, Vol. 11, pp. 80-84, 1971. [13] H. J. Broersma, J. van den Heuvel, B. Jackson, and H. J. Veldman, ``Hamiltonian of regular 2-connected graphs," J. Graph Theory, Vol. 22, pp. 105-124, 1996. [14] M. Y. Chan and S. J. Lee, ``On The Existence of Hamiltonian Circuits in Faulty Hypercubes," SIAM J. Discrete Math., Vol. 4, pp. 511-527, 1991. [15] C. H. Chang, C. K. Lin, H. M. Huang, and L. H. Hsu, ``The super laceability of hypercubes," Information Processing Letters, Vol. 92, pp. 15-21, 2004. [16] Y. H. Chang, C. N. Hung, and C. M. Sun, ``Adjacent vertices fault tolerant hamiltonian laceability of hypercube graphs," Proceedings of the 22nd Workshop on Combinatorial Mathematics and Computation Theory, pp. 301-309, 2005. [17] C. Cooper, A. Frieze, and B. Reed, ``Random regular graphs of non-constant degree: connectivity and hamiltonicity," Combinat. Probability and Computing , Vol. 11, pp. 249-261, 2002. [18] V. Chv¶atal and P. ErdÄos, ``A note on hamiltonian circuits," Discrete math., Vol. 5, pp. 111-113, 1972. [19] V. Chv¶atal, ``Tough graphs and hamiltonian circuits," Discrete math., Vol. 5, pp. 215-228, 1973. [20] G. A. Dirac, ``Some theorems on abstract graphs," Proc. London Math. Soc., Vol. 2, pp. 69-81, 1952. [21] D. A. Du®us, R. J. Gould, and M. S. Jacobson, ``Forbidden subgraphs and the Hamiltonian theme," Theory and Applications of Graphs, Wiley, New York, pp. 297-316, 1981. [22] Y. Egawa and T. Miyamoto, ``The longest cycles in a graph G with minimum degree at least |G|/k," J. Combinat. Theory B, Vol. 46, pp. 356-362, 1989. [23] B. Enomoto, B. Jackson, P. Katerinis, and A. Saito, ``Toughness and the existence of k-factors," J. Graph Theory, Vol. 9, pp. 87-95, 1985. [24] H. Enomoto , A. Kaneko, A. Saito, and B. Wei, ``Long cycles in triangle-free graphs with prescribed independence number and connectivity," J. Combinat. Theory B, Vol. 91, pp. 43-55, 2004. [25] G. Fan, ``Longest cycles in regular graphs," J. Combinat. Theory B, Vol. 39, pp. 325-345, 1985. [26] R. J. Faudree, R. J. Gould, M. S. Gould, M. S. Jacobson , and R. H. Schelp, ``Neighborhood unions and hamiltonian properties in graphs," J. Combinat. Theory B, Vol. 47, pp. 1-9, 1989. [27] T. I. Fenner and A. M. Frieze, ``Halmiltonian cycle in random graphs," J. Combinat. Theory B, Vol. 37, pp. 103-112, 1984. [28] E. Flandrin, I. Fournier, and A. Germa, ``Pancyclism in K_{1,3}-free graphs," Ph.D. Thesis, 1990. [29] E. Flandrin, J. L. Fouquet, and H. Li, ``Halmiltonian of bipartite biclaw-free graphs," Discrete Appl. Math., Vol. 51, pp. 95-102, 1994. [30] H. Fleischner, ``The square of every two-connected graph is hamiltonian," J. Combinat. Theory B, Vol. 16, pp. 29-34, 1974. [31] H. Fleischner, ``In the square of graphs, hamiltonianicity and pancyclicity, hamiltonian connectedness and panconnectedness are equivalent concepts ," Monatsh. Math., Vol. 82, pp. 125-149, 1976. [32] J. S. Fu, ``Fault-tolerant cycle embedding in the hypercube," Parallel Computing, Vol. 29, pp. 821-832, 2003. [33] J. S. Fu, ``Longest fault-free paths in hypercubes with vertex faults," Information Sciences, Vol. 176, pp. 756-771, 2006. [34] S. Goodman, and S. Hedetniemi, ``Sufficient conditions for a graph to be hamiltonian," J. combinat. Theory B, Vol. 16, pp. 175-180, 1974. [35] R. J. Gould, ``Updating the hamiltonian problem-a survey," J. Graph Theory, Vol. 15, no. 2, pp. 121-157, 1991. [36] R. HÄaggkvist, ``Unsolved problem," Proceedings of Fifth Hungarian Colloquim on Combinat., 1976. [37] R. HÄaggkvist and G. G. Nicoghossian, ``A remark on hamiltonian cycles," J. Combinat. Theory B, Vol. 30, pp. 118-120, 1981. [38] J. P. Hayes, ``A graph model for fault-tolerant computing systems," IEEE Transactions on computers, Vol. c25, pp. 875-884, 1976. [39] A. Hobbs, ``The square of a block is vertex pancyclic," J. combinat. Theory B, Vol. 20, pp. 1-4, 1976. [40] D. A. Holton, B. Manvel, and B. D. Mckay, ``Hamiltonian cycles in cubic 3-connected bipartite planar graphs," J. Combinat. Theory B, Vol. 38, pp. 279-295, 1985. [41] S. Y. Hsieh, G. H. Chen, and C. W. Ho, ``Hamiltonian-laceability of star graphs," Networks, Vol. 36, pp. 225-232, 2000. [42] S. Y. Hsieh, ``Fault-tolerant cycle embedding in the hypercubes with more both faulty vertices and faulty edges," Parallel Computing, Vol. 32, pp. 84-91, 2006. [43] B. Jackson and H. Li, ``Hamiltonian cycles in 2-connected regular bipartite graphs," J. Combinat. Theory B, Vol. 62, pp. 236-258, 1994. [44] H. A. Jung, ``On maximal circuits in ¯nite graphs," Ann. Discrete Math., Vol. 3, pp. 129-144, 1978. [45] J. K¶omlos and E. Szemer¶edi, ``Limit distribution for the existence of hamiltonian cycles in random graphs," Discrete Math., Vol. 43, pp. 55-63, 1983. [46] M. Lewinter and W. Widulski, ``Hyper-hamilton laceable and caterpillar-spannable product graphs," Comput. Math. Appl., Vol. 34, pp. 99-104, 1997. [47] M. Li, ``Longest cycles in regular 2-connected claw-free graphs," Discrete Math., Vol. 137, pp. 277-295, 1995. [48] F. Thomson Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, Los Altos, CA, 1992. [49] T. K. Li, C. H. Tsai, Jimmy J. M. Tan, and L. H. Hsu, ``Bipanconnected and edge-fault-tolerant bipancyclic of hypercubes," Information Processing Letters, Vol. 87, pp. 107-110, 2003. [50] C. K. Lin, H. M. Huang, L. H. Hsu and S. Bau, ``Mutually Hamiltonian paths in Star Networks," Networks., Vol. 46, pp. 110-117, 2005. [51] C. K. Lin, H. M. Huang, J. J. M. Tan and L. H. Hsu, ``The Mutually Hamiltonian Cycles of the Pancake Networks and the Star Networks," submitted. [52] X. Liu, ``lower bounds of length of longest cycles in graphs involving neighborhood unions ," Discrete Math., Vol. 169, pp. 133-144, 1997. [53] M. Lipman, ``Hamiltonian cycles and paths in vertex-transitive graphs with abelian and nilpotent groups," Discrete math., Vol. 54, pp. 15-21, 1985. [54] L. Lov¶asz, Combinatorial Structutres and Their Applications. Gordon and Breach, London ``Problem 11," 1970. [55] D. Marusic, ``Hamiltonian paths in vertex-symmetric graphs of order 5p," Discrete math., Vol. 42, pp. 227-242, 1982. [56] J. Mitchem and E. Schmeichel, ``Pancyclic and bipancyclic graphs-a survey," Graphs and Applications, pp. 271-278, 1982. [57] M. M. Matthews, and D. P. Sumner, ``Longest paths and cycles in K1;3-free graphs," J. Graph Theory, Vol. 9, pp. 269-277, 1985. [58] J. Moon and M. Moser, ``On hamiltonian bipartite graphs," Israel J. Math., Vol. 1, pp. 357-369, 1963. [59] O. Ore, ``A note on hamiltonian circuits," Am. Math. Month., Vol. 67, pp. 55, 1960. [60] O. Ore, ``Hamiltonian connected graphs," J. Math. Pures Appl., Vol. 42, pp. 21-27, 1963. [61] O. Ordaz, D. Amar, and A. Raspaud, ``Hamiltonian properties and bipartite independence number," Discrete Math., Vol. 161, pp. 207-215, 1996. [62] L. P¶osa, ``Hamiltonian circuits in random graphs," Discrete Math., Vol. 14, pp. 359-364, 1976. [63] L. B. Richmond, R. W. Robinson, and N. C. Wormald, ``On hamiltonian cycles in 3-connected cubic maps," Ann. Discrete Math., Vol. 27, pp. 141-150, 1985. [64] Y. Saad and M. H. Schultz, ``Topological properties of hypercubes," IEEE Transactions on Computers, Vol. 37, no. 7, pp. 867-872, 1988. 101 [65] A. Sengupta, ``On ring embedding in hypercubes with faulty nodes and links," Information Processing Letters, Vol. 68, pp. 207-214, 1998. [66] G. Simmons, ``Almost all n-dimensional rectangular lattices are hamilton laceable," Congr. Numer., Vol. 21, pp. 649-661, 1978. [67] J. E. Simpson, Hamiltonian bipartite graphs," Congr. Numer., Vol. 85, pp. 97-110, 1991. [68] Z. M. Song, Y. S. Qin, ``A new su±cient condition for panconnected graphs," Ars Combin., Vol. 34, pp. 161-166, 1992. [69] H. Trommel, H. J. Veldman, and A. Verschut, ``Pancyclicity of claw-free hamiltonian graphs ," Discrete Math., Vol. 197/198, pp. 781-789, 1999. [70] Y. C. Tseng, ``Embedding a ring in a hypercube with both faulty links and faulty nodes," Information Processing Letter, Vol. 59, pp. 217-222, 1996. [71] C. H. Tsai, J. M. Tan, T. Liang and L. H. Hsu, ``Fault-tolerant hamiltonian laceability of hypercubes," Information Processing Letters, Vol. 83, pp. 301-306, 2002. [72] Chang-Hsiung Tsai, ``Linear array and ring embeddings in conditional faulty hypercubes," Theoretical Computer Science 314, pp. 431-443, 2004. [73] A. S. Vaidya, P. S. N. Rao, and S. R. Shankar ``A class of hypercube-like networks," in: Pro. of the 5th Symp. On Parallel and Distributed Processing,IEEE Comput. Soc., Los alamitos, CA, December, pp. 800-803, 1993. [74] B.Wei, ``Hamiltonian paths and hamiltonian connectivity in graphs," Discrete Math., Vol. 121, pp. 223-228, 1993. [75] J. M. Xu, ``Edge-fault-tolerant edge-bipancyclicity of hypercubes," Information Processing Letter, Vol. 96, pp. 146-150, 2005. [76] C. Q. Zhan, ``Hamiltonian cycles in claw-free graphs," J. Graph Theory, Vol. 12, pp. 209-216, 1988. [77] C. Q. Zhang and Y. J. Zhu, ``Long path connectivity of regular graphs," Discrete Math., Vol. 96, pp. 151-160, 1991. [78] Y. J. Zhu, Z. H. Liu, and Z. G. Yu, ``An improvement of Jackson's result on hamiltonian cycles in 2-connected regular graphs," Cycles in Graphs (Burnaby, B.C., 1982), North Holland Mathematics Studies, Vol. 115, North Holland, Amsterdam, pp. 237-247, 1985.
指導教授	黃華民(Hua-Min Huang)	審核日期	2006-5-20
推文	facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu
網路書籤	Google bookmarks   del.icio.us   hemidemi   myshare