The Fault-tolerant Cycles Or Paths In Three Kinds Of Network

On the interconnection networks, a structure can be used to simulate another is very important. Network simulation problem can be reduced to graph embedding problem. Thus, studying graph embedding capacity is one of the central issues in designing and evaluating an interconnection networks.paths and cycles are two pop-ular networks for designing simple parallel processing and distributed computation with simple structure, small degree and low communication cost. If one network contains paths or cycles of variabe lengths, it can effectively simulate many algo-rithms designed on linear arrays or rings. Therefore, it is meaningful to study the pancyclicity or panconnectivity of interconnection networks. Since faults may hap-pen when a network is put into use, it is important and practically meaningful to consider faulty interconnection networks.The hypercube, folded hypercube and complete graph are three common in-terconnection networks. The n-dimensional hypercube, denoted Qn, is an n-regular n-connected bipartite graph with 2n vertices. The n-dimensional folded hypercube, denoted FQn, is an attractive variance of an n-dimensional hypercube Qn. It is an (n+1)-regular (n+1)-connected graph with 2n vertices. The complete graph on n vertices,denoted Kn, is a simple graph in which any two vertices are adjacent. It is an (n-1)-regular (n-1)-connected graph. These three classes of networks have widely been used in parallel processing and distributed computating system.In this thesis,we consider the following three problems:1,The problem of fault-free cycles or paths are embedded in faulty hypercubes.2,The problem of edge-fault-tolerant panconnectivity of the folded hypercubes. and3,The problem of fault-tolerant panconnectivity of the complete graph.We obtained the following five results:1,For 3≤h≤n, let Fv and Fe denotes a set of faulty vertices and edges in Qn,respectively,such that |Fv|+|Fe|≤n-h.Then,every path P with length h lies on a cycle in Qn-Fv-Fe of every even length from 2h+2 to 2n-2|Fv| inclusive.Moreover,the path P lies on a cycle in Qn-Fv-Fe of length 2h when |Fe|+|Fv|