High - Order Connectivity Of K - K Cubes

Along with the advance of VLSI circuit technology, it has become possible to develop high-performance large scale multiprocessor systems comprising hundreds of thousands of processors. The connected model between various processors is called an interconnection network. It is often modeled as an undirected simple graph, in which the vertices corresponds to processors, and the edges corresponds to communication links. In the process of system operation, the processor failure is inevitable. Therefore, in designing or selecting a network topology for large scale multiprocessor systems, one fundamental consideration is reliability.To some extent, connectivity can measure the reliability of the system. However, tradi-tional connectivity has certain defects to measure the reliability of interconnection network. For overcoming these deficiencies, Latifi et al. and Fiol put forward the concepts of Rg-connectivity(called kg) and h-extraconnectivity(called kh) respectively. It has been shown that the larger the Rg-connectivity (the h-extraconnectivity) is, the more reliable the network is. When Rg-connectivity (h-extraconnectivity) is certain, the fewer of the Rg-cut (h-extra cut) is, the more reliable the network is.As a generalization of hypercube, k-ary n-cube is a very important network. For example the Cray T3D, J-machine and iWarp have been built with k-ary n-cubes forming the underlying topology. In this paper, we mainly study the Rg-connectivity and h-extraconnectivity of k-ary n-cubes.This thesis consisits of four chapters. In Chapter1, we first introduce the application background and research status of g-connectivity and h-extraconnectivity of interconnection network; Next, we introduce the basic notation and terminology on graphs; After that, we present the concept and some properties of k-ary n-cubes; Finally, the main contents and results of this paper are listed.In Chapter2, we mainly study the Rg-connectivity of3-ary n-cube kg(Qn3). An Rg-cut of a graph G is a vertex set F such that G-F is disconnected and every vertex ot G-F has at least g neighbors in G-F. The Rg-connectivity of a graph G, k9(G), is the cardinality of the minimum Rg-cut. We get the following main results:(a) Let g be an integer with0≤g≤n-1. If g is even, the Rg-connectivity of3-ary n-cube kg(Qn3)=3g/2(2n-g):Otherwise, the Rg-connectivity of3-ary n-cube kg(Qn3)=3g-1/2-(4n-2g-1).(b) Let g, n be two integers with0≤g≤n-2, and let F be a minimum Rg-cut of Qn3, B be a minimum component of Qn3-F. Then B(?) Qg3if k is even; Otherwise B(?)Q3g-1/×K2.Following Chapter2. Chapter3mainly studies the Rg-connectivity of k-ary n-cube kg(Qnk) when k≤4. By studying the neighbors of the subgraph H(?) Qg of Qnk, which is diffrent from the method of Chapter2, we get the following main result:Let g, n be two integers with0≤g≤n. n≥3. Then Kg(Qnk)=(2n-2)2g. In Chapter4, we mainly study the h-extraconnectivity of3-ary n-cube kh(Qn3).For a connected graph G, a vertex cut F of G is an h-extra, cut if G-F is disconnected and every component of G-F has more than h vertices. The h-extraconnectivity of G, kh(G), is defined as the cardinality of a minimum h-cxtra cut. We get the following main results:(a) Let0≤h≤n. n≥3. Then the h-extraconncctivity of3-ary n-cube Kh(Qn3)=(h+1)2n-3h-Ch2(Ch2is a Combination, that is h(h-1)/2).(b) Let F be a smallest h-extra cut of3-ary n-cube, where0≤h≤n-1,n≥3, and h≠3. Then every smallest component H of Qn3-F is isomorphic to K1,h and any three vertices of H do not lie on the same triangle of Qn3.(c) Let h,n be two integers with0≤h≤n-1,n≥3, h≠3, and let F be a smallest h-cxtra cut of Qn3. Then F is precisely the neighborhood of some subgraph H (?) Qn3, where H(?)K1,h and any three vertices of H do not lie on the same triangle of Qn3.