| An interconnection network is usually modeled by an undirected graph G. The sets of vertices and edges of G are denoted by V(G) and E(G), respectively represents processorsand links between processors. In interconnection networks, one of the important issues in designing and evaluating an interconnection network is to study how well other existing networks can be embedded into this network. This problem can be modeled by graph embedding problem. Linear arrays and rings (i.e. cycles) are two fundamental networks for parallel and distributed computation. Many efficient algorithms were originallydesigned based on linear arrays and rings for solving a variety of graph problems and some parallel applications, such as those in image and signal processing. Thus, it is important to have an effective path and cycle embedding in a networks. The path and cycle embedding properties of many interconnection networks have been investigated in the literature. Since faults may happen when a network is put in use, it is significantto consider faulty networks. Fault-tolerance ability is a very important issue of interconnection networks. Among all the interconnection network topologies proposed in the literature, hypercubes denoted by Q_n, is one of the most popular topologies. Very recently, bubble-sort graphs denoted by B_n, which belong to the class of Cayley graphs, have been attractive alternative to hypercubes. It has some good topological properties such as highly symmetry and recursive structure.In this dissertation, we discuss the embedding of paths and cycles into (faulty) Bubble-sort network and hypercubes. It consists of 6 chapters, in which the 3rd chapter to the 5th chapter are main parts.In the 1st chapter, we introduce the background of our works.In the 2nd chapter, we first introduce terminology and notation of graph theory. Then we introduce the concepts of embedding and fault-tolerance. Furthermore, we give the definitions and some proposition of Bubble-sort networks and hypercubes. Finally, we list some known results on the topic.In the 3rd chapter, we study basic propositions of Bubble-sort network, we first obtain the super connectivity and super edge-connectivity.1. For n≥3,κ'(B_n) = 2n - 4. For n≥5,λ'(B_n) = 2n - 4. Then we obtain the bipanconnectivity of Bubble-sort networks.2. For n≥5, every pair nodes x , y in B_n, there exists a xy-path of length l with d(x,y)+2≤l≤n!-1,2|(l-d(x,y)).In the 4th chapter, we study the embedding of paths into Bubble-sort networks with faulty vertices. We obtain the following main results.1. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. Any pair different colored vertices x and y in B_n-F_v, there exists xy- path of length n!-2f_v-1.According to the above result, we obtain:2. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. In B_n-F_v, there exists cycle of length n!-2|F_v|.3. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. Any pair same colored vertices x and y in B_n-F_v, there exists xy- path of length n!-2|F_v|-2.In the 5th chapter, we study the embedding of Bubble-sort networks and hypercubes with faulty edges. We obtain the following main results.1. For n≥5, faulty edges set F_e of B_n with |F_e|≤n-3. Every edge of B_n-F_v, lies on even cycle of length l, 6≤l≤n!.2. For n≥4, faulty edges set F_e of B_n with |F_e|≤2n-7 and every vertex of B_n-F_e incident with at least 2 non-faulty edges, there exists Hamilton cycle.3. For n≥4, faulty edges set F_e of B_n with |F_e|≤2n-7 and every vertex of B_n-F_e incident with at least 2 non-faulty edges, there exists even cycle of length￡, 6≤l≤n!.4. For n≥4, faulty edges set F_e of Q_n with |F_e|≤n-1 and not all faulty edges incident with 1 vertex, every pair nodes u, v in Q_n-F_e, there exists a uv-path of length l with d(x,y)+4≤l≤2~n-1, 2|(l-d(x,y)).In the 6th chapter, we conclude our results and give some conjectures and problems to be studied further.In the Appendix, we give the data used in our proof.
|
PDF Full Text Request