一些一般化蜂窩環輪面的漢米爾頓可蕾絲性質

The Hamiltonian Laceability of some Generalized Honeycomb Tori

林東毅(Tung-Yi Lin)

指導教授 ： 高欣欣

中原大學/理學院/應用數學系/碩士(2007年)

https://doi.org/10.6840/cycu200700207

摘要

設m，n和s為整數，m≧2、n≧4、0≦s≦n且m+s為偶數。在平行和分散式的網際網路中，有一種名為一般化蜂窩環輪面(Generalized Honeycomb Tori GHT(m,n,s))的圖形被廣泛應用。我們已經知道GHT(m,n,s)為三正則圖，二分圖且為漢米爾頓圖。在本篇文章裡，我們所關心的是GHT(m,n,n/2)與GHT(m,n,0)這兩種圖。令G=GHT(m,n,s)，s為n/2或0。我們證明G為漢米爾頓可蕾絲圖。更明確地說，只要給定一對點x與y，且x與y分屬於兩個不同的二分集，那麼一定可以找到一條路徑Q使得Q包含x、y與G 上的所有頂點。

關鍵字

漢米爾頓可蕾絲圖 ； 一般化的蜂窩環輪面 ； 蜂窩環輪面 ； 網際網路應用

並列摘要

Assume that m , n and s are integers with m>=2 , n>=4 , 0<=s<=n and s is of the same parity of m. The generalized honeycomb torus GHT(m,n,s) is recognized as another attractive alternative to existing torus interconnection networks in parallel and distributed applications. It is known that any GHT(m,n,s) is 3-regular, hamiltonian, bipartite graph. We are interested in two special types of the generalized honeycomb torus, GHT(m,n,n/2) and GHT(m,n,0). Let G=GHT(m,n,s), where s belong to {n/2,0}. We prove that any G is hamiltonian laceable. More precisely, for any two vertices x and y from different partite set of G, there exists a path Q joining x and y such that Q contains all vertices of G.

並列關鍵字

Generalized Honeycomb Torus ； Interconnection networks ； Hamiltonian Laceable ； Honeycomb torus

參考文獻

2.I. Stojmenovic,"Honeycomb Networks: Topological Properties and Communication Algorithms",IEEE Trans. Parallel and Distributed Systems, vol.8, 1997, pp.1036--1042.

3.J. Carle, J-F. Myoupo, and D. Seme,"All-to-All Broadcasting Algorithms on Honeycomb Networks and Applications", Parallel Processing Letters, vol.9, 1999, pp.539--550.

4.G.M. Megson, X. Yang, and X. Liu,"Honeycomb Tori are Hamiltonian",Information Processing

Letters, vol.72, 1999, pp.99--103.

5.G.M. Megson, X. Liu, and X. Yang,"Fault-Tolerant Ring Embedding in a Honeycomb Torus with Nodes Failures", Parallel Processing Letters, vol.9, 1999, pp.551--561.