交換網路的互斥漢米爾頓性質與生成連通性的研究

Abstract

Menger在1972證明「圖G中任兩個相異點都存在著k條不相交的路徑若且為若圖G的是k連通」。如果圖G任兩個相異點都存在著k條不相交的路徑，同時此k條不相交的路徑會通過圖G所有的點，則稱圖G為k*連通。圖G的生成連通度□*(G)是最大的整數k，使得對所有不大於k的值w，圖G為w*連通。我們將針對一部分的交換網路與圖形研究其生成連通度。

在圖形理論的研究中，圈嵌入和路徑嵌入的問題一直是重要的研究議題。圖G的一個漢米爾頓圈C可以依經過的次序描述為< u1, u2, …, un(G), u1 >。因此，我們稱u1為C的起始點而稱ui為C的第i個點。假如圖G的兩個漢米爾頓圈 C1 = < u1, u2, …, un(G), u1 > 和C2 = < v1, v2, …, vn(G), v1 > 的起始點相同且除了起始點和最後一個點之外彼此的第i個點都不相同，則稱這兩個漢米爾頓圈彼此獨立。假如圖G的漢米爾頓圈的集合{ C1, C2, …, Ck }之中的漢米爾頓圈兩兩獨立，則稱這個集合為互相獨立。圖G任給一個點u作為起始點至少都能找到的互相獨立的漢米爾頓圈的個數的最大值，稱為圖G的互相獨立漢彌爾頓度。我們將探討一部分的交換網路與圖形的互相獨立漢彌爾頓度。

The Menger Theorem (Menger, 1972) show that there are k-disjoint paths between any two distinct vertices of G if and only if G is k-connected. A graph G is k*-connected if there exists a k-disjoint paths between any two distinct vertices which contains all the vertices of G. The spanning connectivity of G, k*(G), is defined as the largest integer k such that G is w*-connected for 0 < e w < k+1 if G is a 1*-connected graph. We study the problem of spanning connectivity properties on some interconnection networks and graphs.

Cycle embedding and path embedding are perhaps the most important outstanding materials in graph theory and have been defying solutions for more than a century. A hamiltonian cycle C of graph G is described as < u1, u2, ..., un(G), u1 > to emphasize the order of vertices in C. Thus, u1 is the starting vertex and ui is the i-th vertex in C. Two hamiltonian cycles C1 = < u1, u2, ..., un(G), u1 > and C2 = < v1, v2, ..., vn(G), v1 > of G are independent if u1 = v1 and ui is not equal to vi for every i in { 2, ..., n(G) }. A set of hamiltonian cycles { C1, C2, ..., Ck } of G are mutually independent if its elements are pairwise independent. The mutually independent hamiltonianicity IHC(G) of graph G the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u. We study this problem on some interconnection networks and graphs.