廣義超立方體中滿足要求長度之雙互斥擴展路徑

Two Spanning Disjoint Paths with Required Length in Generalized Hypercubes

林耀鐘(Yao-Chung Lin)

指導教授 ： 杜迪榕

國立暨南國際大學/科技學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6837/NCNU.2011.00094

摘要

這個研究調查廣義超立方體圖滿足要求長度之雙互斥擴展路徑特性。在廣義超立方體圖中給定任意四相異點u、v、x與y，令l1和l2為兩整數，使得l1 (l2) 不小於u和v (x和y)之間的距離，且l1加l2等於廣義超立方體圖中節點個數減二。然後在排除一些特殊條件後，存在有雙互斥路徑P1和P2使得：(1) P1是一條由u連接到v的路徑，且P1長度等於l1；(2) P2是一條由x連接到y的路徑，且P2長度等於l2；(3) P1∪P2擴展整個廣義超立方體圖。這個研究證明一個廣義超立方體圖滿足要求長度之雙互斥擴展路徑特性，當該廣義超立方體圖之每一維度之節點個數皆大於或等於4。

關鍵字

雙互斥擴展路徑 ； 廣義超立方體 ； 互斥路徑 ； 漢彌爾頓連接 ； 路徑嵌入

並列摘要

This work investigates 2RP-property of a generalized hypercube G. Given any four distinct vertices u, v, x and y in G, let l1 and l2 be two integers such that l1 (l2) is not less than the distance between u and v (x and y), and l1+l2 is equal to the number of vertices in G minus two. Then, there exist two vertex-disjoint paths P1 and P2 such that (1) P1 is a path joining u and v with length of l1; (2) P2 is a path joining x and y with length of l2, and (3) P1 ∪ P2 spans G except some special conditions. This work shows that a r-dimensional generalized hypercube, denoted by G(mr, mr-1, …, m1), satisfies 2RP-property, where mi≧4 for all 1≦i≦r.

並列關鍵字

2RP-property ； generalized hypercube ； vertex-disjoint paths ； Hamiltonian-connected ； path embedding

參考文獻

[1] L.N. Bhuyan and D.P. Agrawal, “Generalized hypercube and hyperbus structures for a computer network,” IEEE Transactions on Computers, vol. 33, no. 4, pp. 323?333, 1984.

[2] F. Cao, D.Z. Du, D.F. Hsu, S.H. Teng, “Fault tolerance properties of pyramid networks,” IEEE Transactions on Computers, vol. 48, no. 1, pp. 88?93, 1999.

[3] J.M. Chang, J.S. Yang, Y.L. Wang, and Y. Cheng, “Panconnectivity, fault-tolerant hamiltonicity and Hamiltonian connectivity in alternating group graphs,” Networks, vol. 44, no. 4, pp. 302?310, 2004.

[4] D.R. Chen and C.C. Hsu, “Fault-tolerant routing for pyramid networks using the least level minimal routing method,” Computer Systems: Science & Engineering, vol. 18, no. 1, pp. 35?44, 2003.

[5] G.H. Chen and D.R. Duh, “Topological properties, communication, and computation on WK-recursive networks, Networks, vol. 24, no. 6, pp. 303?317, 1994.