連結網路上之多重資料傳輸及連通性研究

Abstract

在這次的計劃中，我們要研討一個最近新提出的性質，稱為強Menger 連通性。假設一 網路G有一壞點集合F，令G-F為移去F之後的網路。若G - F中每對點u與點v被min{degf (u), degf (v)}點相異路徑所連接，其中degf (u)和degf (v)分別為G - F中點u與點v的分支度， 則我們稱圖G 為強Menger 連通。我們已針對hypercube-like networks 及matching composition networks研究了它們的強Menger連通性，及強Menger連通性的容錯程度。我 們將對其它的連接網路，研究其強Menger連通性。對於以上的主題，我們已經有一些結 果發表或審查中在著名的國際期刊上。並且我們對於這個主題還有一些新的構想並對其 做深入的研究。  Lun-Min Shih, Chieh-Feng Chiang, Lih-Hsing Hsu, and Jimmy J.M. Tan, "Strong Menger Connectivity with Conditional Faults on the Class of Hypercube-like Networks," Information Processing Letters, Vol. 106, pp. 64-69, 2008.【SCI】  Lun-Min Shih, Chieh-Feng Chiang, Tsung-Han Tsai, Lih-Hsing Hsu, Jimmy J.M. Tan, "Maximal Local-Connectivity on the Matching Composition Networks with Faulty Elements," submitted to Information Sciences. 另一個在本次計劃中，我們還要討論另一項議題，我們將會研究另一個較強的性 質，稱之為相互獨立泛連通性。兩個等長的路徑P1=< u1,u2,…,um> 和P2=<v1,v2,…,vm> 從 點a出發到點b是獨立的，如果u1=v1=a，um=vm=b，且ui vi對於2  i  m-1。一個等長路 徑的集合{P1,P2,…,Pn}從點a出發到點，如果這個集合中任意一對的路徑是獨立的，則稱 這個集合是相互獨立的。假設點u和點v是在二部圖G上的任意兩個不相同的點，l是一個 長度為正整數，dG(u,v)  l  |V(G)-1|且(l-dG(u,v))是偶數。我們說點u和點v是(m,l)-相互獨 立泛連通，如果存在m個相互獨立的路徑{P1 l, P2 l,…, Pm l}且它們從點u到點v的長度是l。 在各個連接網路中找出最多的兩兩相互獨立路徑，是我們提出的一個新穎的研究題目。 對於以上的主題，我們已經有一些結果發表或審查中在著名的國際期刊上。並且我們對 於這個主題還有一些新的構想並對其做深入的研究。  Cheng-Kuan Lin, Jimmy J.M. Tan, Hua-Min Huang, D. F. Hsu, and Lih-Hsing Hsu, "Mutually independent hamiltonian cycles for the pancake graphs and the star graphs," Discrete Mathematics, Vol. 309 pp. 5474-5483, 2009. 【SCI】  Yuan-Kang Shih, Jimmy J.M. Tan, and Lih-Hsing Hsu, "Mutually Independent Bipanconnected Property of Hypercube,” submitted to Applied Mathematics and Computation. 這些概念對於連結網路的研究是有趣且有用的。我們將在本次計劃中，將對一些著 名連結網路的強Menger連通性質與相互獨立泛連通性質作深入的研究。

In this project, we will study the newly proposed concept called strong Menger connectivity. Suppose that a network G has a set F of faulty vertices and let G−F be the resulting network with those vertices in F removed. We say that a k-regular graph G is strongly Menger connected if each pair u and v of G−F are connected by min{degf (u), degf (v)} vertex-disjoint fault-free paths in G−F, where degf (u) and degf (v) are the degree of u and v in G − F, respectively. About this issue, we already had some results published and submitted to the international journals. We have some new ideas about this issue and expect to study more thorough.  Lun-Min Shih, Chieh-Feng Chiang, Lih-Hsing Hsu, and Jimmy J.M. Tan, "Strong Menger Connectivity with Conditional Faults on the Class of Hypercube-like Networks," Information Processing Letters, Vol. 106, pp. 64-69, 2008.【SCI】  Lun-Min Shih, Chieh-Feng Chiang, Tsung-Han Tsai, Lih-Hsing Hsu, Jimmy J.M. Tan, "Maximal Local-Connectivity on the Matching Composition Networks with Faulty Elements," submitted to Information Sciences. The other issue of this project, we will study another strong property called mutually independent bipanconnected property. Two paths with equal length P1=< u1,u2,…,um> and P2=<v1,v2,…,vm> from a to b are independent if u1=v1=a, um=vm=b, and ui vi for 2  i  m-1. Paths with equal length {P1,P2,…,Pn} from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, dG(u,v)  l  |V(G)-1| with (l-dG(u,v)) being even. We say that the pair of vertices u, v is (m,l)-mutually independent bipanconnected if there exist m mutually independent paths {P1 l, P2 l,…, Pm l}with length l from u to v. About this issue, we already had some results published and submitted to the international journals. We have some new ideas about this issue and expect to study more thorough.  Cheng-Kuan Lin, Jimmy J.M. Tan, Hua-Min Huang, D. F. Hsu, and Lih-Hsing Hsu, "Mutually independent hamiltonian cycles for the pancake graphs and the star graphs," Discrete Mathematics, Vol. 309 pp. 5474-5483, 2009. 【SCI】  Yuan-Kang Shih, Jimmy J.M. Tan, and Lih-Hsing Hsu, "Mutually Independent Bipanconnected Property of Hypercube,” submitted to Applied Mathematics and Computation. These two concepts are both interesting and useful in the study of interconnection networks. In this project, we will study the strong Menger property and mutually independent bipanconnected property of many existing practical interconnection networks.