某些一般性蜂窩環輪面的二部三連通性及強二部三連通性研究

The Bi-3*-connectivity and Strong Bi-3*-connectivity of Some Generalized Honeycomb Tori

林怡瑜(Yi-Yu Lin)

指導教授 ： 高欣欣

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

https://doi.org/10.6840/cycu200800368

摘要

假設m，n和s為整數，m >= 2，n >= 4，0 <= s < n，其中 n 為偶數，而 s與 m同為奇數或同為偶數。在平行和分散式的網際網路中，有一種名為「一般性蜂窩環輪面」(Generalized Honeycomb Tori), GHT(m,n,s) ,的圖形被廣泛應用。我們已經知道任何一般性蜂窩環輪面 GHT(m,n,s) 為三正則，有漢米爾頓迴圈，且為二部圖。在本篇文章裡，我們所感興趣的是針對 s=n/2 時的一般性蜂窩環輪面， GHT(m,n,n/2)。令 G(V,E)=GHT(m,n,n/2)，其中 V 是圖 G 中的點集合且E 是圖 G 中的邊集合，我們證明只要給定任何一對點 u 與 v ，且 u 和 v 分屬於兩個不同顏色的點集合，那麼一定可以找到三條路徑使得這三條路徑連結 u 、 v ，且通過 G上所有的點。 另外，給定一對點 u 與 v 且 u 和 v 屬於相同顏色的點集合 W，則存在一點 w 屬於 W ， 使我們能找到連結 u、v 的三條路徑，且此三條路徑通過 V-{w} 中所有的點。

關鍵字

超二部三連通圖. ； 蜂窩環輪面 ； 二部三連通圖 ； 全域三連通圖 ； 強二部三連通圖

並列摘要

Assume that m , n and s are integers with m >=2 , n>= 4 , 0 <= s < n , n is even , 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 a 3-regular, hamiltonian, bipartite graph. In this paper, we are interested in one special type of the generalized honeycomb torus, GHT(m,n,n/2). Let G(V,E)=GHT(m,n,n/2), where V is the vertex set and E is the edge set of G. We show that for any pair of vertices u and v of the opposite partite sets of G, there exist three disjoint paths between u and v such that the union of these three paths covers V. In addition, given a pair of vertices u and v of the same partite set of G, which is denoted by W(C= V), there exists a vertex w Є W such that there exist three disjoint paths between u and v and the union of these three paths covers V-{w}.

並列關鍵字

strong bi-3*-connectivity ； hyper bi-3*-connectivity. ； globally 3*-connected ； honeycomb torus ； bi-3*-connectivity

參考文獻

[2] I. Stojmenovic, Honeycomb Networks: Topological Properties and Communication Algorithms, IEEE Trans. Parallel and Distrib. Syst. 8 (1997), 1036─1042.

[3] J. Carle, J-F. Myoupo, and D. Seme, All-to-All Broadcasting Algorithms on Honeycomb Networks and Applications, Parallel Process. Lett. 9 (1999), 539--550.

[4] G.M. Megson, X. Yang, and X. Liu, Honeycomb Tori Are Hamiltonian, Inf. Process. Lett.72 (1999), 99--103.

[5] G.M. Megson, X. Liu, and X. Yang, Fault-Tolerant Ring Embedding in a Honeycomb Torus with Nodes Failures, Parallel Process. Lett. 9 (1999), 551--561.

[6] B. Parhami and D.M. Kwai, An Unified Formulation of Honeycomb and Diamond Networks, IEEE Trans. Parallel and Distrib. Syst. 12 (2001), 74--80.