在平衡超立方體上建構完全獨立擴展樹

Constructing Completely Independent Spanning Trees in Balanced Hypercubes

楊臆仙(Yi-Xian Yang)

指導教授 ： 張肇明 ； 白恭瑞

國立臺北商業大學/管理學院/資訊與決策科學研究所/碩士(2020年)

摘要

令T1,T2,...,Tk 是圖G上的k棵擴展樹，對任何兩點u和v所連接的路徑在 k 棵樹上不會用到相同的點和邊，除了 u 和 v 之外。那麼 T1, T2, ..., Tk 就被稱為是在圖 G 上的一組完全獨立擴展樹。建構完全獨立擴展樹可以應用在連結網路上的容錯與安全的訊息傳輸。在本論中，我們探討在平衡超立方體上建構兩棵完全獨立擴展樹的問題。平衡超立方體是一個變形的超立方體，並且有優於超立方體的直徑。研究結果，我們在二維度的平衡超立方體 BH2 上，所建構的兩棵完全獨立擴展樹，它的直徑為 9。當在三維度以上 n ≥ 3 的 BHn 上，兩棵完全獨立擴展樹的直徑為 6n − 2。

關鍵字

連結網路 ； 完全獨立擴展樹 ； 平衡超立方體 ； 直徑

並列摘要

A set of spanning trees of a graph G is called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y ∈ V (G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n−2forBHn when n≥3.

並列關鍵字

interconnection networks ； completely independent spanning trees ； balanced hypercubes ； diameter

參考文獻

[1] T. Araki, Dirac’s condition for completely independent spanning trees, Journal of Graph Theory, 77 (2014) 171–179.

[2] J.-M. Chang, H.-Y. Chang, H.-L. Wang, K.-J. Pai, and J.-S. Yang, Completely independent spanning trees on 4-regular chordal rings, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E100-A (2017) 1932–1935.

[3] H.-Y. Chang, H.-L. Wang, J.-S. Yang, and J.-M. Chang, A note on the degree condition of completely independent spanning trees, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E98-A (2015) 2191–2193.

[4] D.-Q. Cheng, R.-X. Hao, and Y.-Q. Feng, Two node-disjoint paths in balanced hypercubes, Applied Mathematics and Computation, 242 (2014) 127–142.

[5] B. Cheng, D. Wang, and J. Fan, Constructing completely independent spanning trees in crossed cubes, Discrete Applied Mathematics, 219 (2017) 100–109.