臺灣博碩士論文加值系統

令 T1, T2, …, Tk 為圖 G 上的 k 棵擴展樹，對任何兩點 u 和 v 所構成的路徑在 k 棵樹上除了 u 和 v 之外不會使用到相同的點和邊，那麼 T1, T2, …, Tk 就被稱之為是在圖 G 上的一組完全獨立擴展樹。完全獨立擴展樹的建構可以被應用在互連網路上廣播的容錯和安全的訊息傳布。在本篇論文中，我們提出一個圖 G 它的點數量 n 至少 6 以上且每一點的分支度至少 n - 2 的情況下，我們可以造出 ⌊ n/3 ⌋ 棵完全獨立擴展樹。另外我們也提出在 4 連通的弦環網路CR(N , d)，滿足 N ≥ 5 且 d = ⌈ N/2 ⌉ -1 或者 N 和 d 皆是正偶數的情況下，我們可以造出兩顆完全獨立擴展樹。

In a graph G, a set of spanning trees are said to be completely independent if for any vertices u and v, the paths connecting them on the spanning trees have neither vertex nor edge in common, except u and v. In this thesis, we prove that for graphs of order n, with n ≥ 6, if the minimum degree is at least n - 2, then there are
⌊ n/3 ⌋ completely independent spanning trees. Also, we show that there are two completely independent spanning trees on chordal rings CR(N,d), where N ≥ 5 and
d = ⌈ N/2 ⌉ -1 or both N and d are even integers.

摘要 I
Abstract II
誌謝 III
Contents V
List of Tables VII
List of Figures VIII
1 Introduction 1
1.1 Background . . . . . . . . . . . . . .. . . . . . 1
1.2 Motivation and Intentions . . . . . . . . . . . .2
1.3 Outline of the Thesis . . . . . . . . . . . . . . .3
2 Preliminaries 4
2.1 Definitions and Notation . . . . . . . . . . . . 4
2.2 Problem Definition . . . . . . . . . . . . . . . 5
2.3 Historical Review . . . . . . . . . . . . . . . 6
3 Main Results 12
3.1 Degree condition of completely independent spanning trees . . .12
3.1.1 For even n . . . . . . . . . . . . . . . . . . 12
3.1.2 For odd n . . . . . . . . . . . . . . . .. . . 14
3.1.3 Proof of Theorem 3.1 . . . . . . . . . . . . . 16
3.2 Completely independent spanning trees on chordal rings . . . . . . . 16
4 Conclusions and Future Work 22
4.1 Conclusions . . . . . . . . . . . . . . . . . . 22
4.2 Future Work . . . . . . . . . . . . . . . . . . 22
Bibliography 23

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

[2] N. Chalamaiah and B. Ramamurthy, Finding shortest paths in distributed loop networks, Information Processing Letters, 67 (1998) 157-161.

[3] G. Fan, Y. Hong and Q. Liu, Ore's condition for completely independent spanning trees, Discrete Applied Mathematics, 177 (2014) 95-100.

[4] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass, 1969.

[5] T. Hasunuma and C. Morisaka, Completely independent spanning trees in torus networks, Networks, 60 (2012) 235-245.

[6] T. Hasunuma, Completely independent spanning trees in the underlying graph of a line graph, Discrete Mathematics, 234 (2001) 149-157.

[7] T. Hasunuma, Completely independent spanning trees in maximal planar graphs, Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), Lecture Notes in Computer Science, 2537 (2002) 235-245.

[8] Y. Iwasaki, Y. Kajiwara, K. Obokata and Y. Igarashi, Independent spanning trees of chordal rings, Information Processing Letters, 69 (1999) 155-160.

[9] K. Mukhopadhyaya and B.P. Sinha, Fault-tolerant routing in distributed loop networks, IEEE Transactions on Computers, 44 (1995) 1452-1456.

[10] L. Narayanan and J. Opatrny, Compact routing on chordal rings of degree 4, Algorithmica, 23 (1999) 72-96.

[11] K.-J. Pai, S.-M. Tang, J.-M. Chang and J.-S. Yang, Completely independent spanning trees on complete graphs, complete bipartite graphs and complete tripartite graphs, in: Proc. 3rd Int. Computer Symp. (ICS 2012), Dec. 12-14,
Hualien, Taiwan. R.-S. Chang et al. (Eds.): Advances in Intelligent Systems and Applications Vol. 1, SIST 20, Springer, pp. 107-113.

[12] K.-J. Pai, J.-S. Yang, S.-C. Yao, S.-M. Tang and J.-M. Chang, Completely independent spanning trees on some interconnection networks, IEICE Transactions on Information and Systems, 97-D (2014) 2514-2517.

[13] F. P_eterfalvi, Two counterexamples on completely independent spanning trees, Discrete Mathematics, 312 (2012) 808-810.

[14] J.-S. Yang, J.-M. Chang, S.-M. Tang and Y.-L. Wang, Reducing the height of independent spanning trees in chordal rings, IEEE Transactions on Parallel and Distributed Systems, 18 (2007) 644-657.

[15] G.W. Zimmerman and A.H. Esfahanian, Chordal rings as fault-tolerant loops, Discrete Applied Mathematics, 37/38 (1992) 563-573.