Edge Fault-tolerant Of Ring Embedded In Torus Network

The mode of connection between components in computer system or communication system is called an interconnection network of the system.Interconnection network is usually represented by a graph, where vertices represent processors and edges represent communication links between processors. With the increase of size of multicomputer systems, it becomes more likely that there exist faults in a system. Fault tolerance will becomes a critical issue in the process of information transfer between different processors.Therefore, we need to design a new network model of fault-tolerant in order to accommodate more mistakes. As one of the most fundamental class of network topology, the cycle can be embedded in a network, which is important for solving some optimization problems because of it represents data flow structures for many parallel algorithms. In this paper, we study the fault-tolerance and cycle embedding for two special torus networks.For the two-dimensional torus network, we mainly study the edge fault-tolerant and the longest cycle embedded. And get the result:two-dimensional torus( m, n)(where m, n ? 5 are integers), with at most four faulty edges is hamiltonian if the following two fault-tolerant conditions are satisfied:(1) the degree of every vertex is at least two, and(2) there is no any forbidden 4-cycle.For the 2-ary n-dimensional torus network(that is, n-dimensional hypercube, denoted byQn, where n ?2 is integer), we considered the edges fault-tolerant and cycles of even length embedded. And get the result:Qn(where n ?5 is integer), with at most 3n-8 faulty edges contains a cycle of every even length from 4 to|V(Qn)| if the following two fault-tolerant conditions are satisfied:(1) the degree of every vertex is at least two, and(2) there is no any forbidden4-cycle.In the aspects of fault-tolerance and hamiltonian cycle embedding for n-dimensional hypercube. When weintroduce a new fault model and improvethe number of allowed fault edges 3n-8 to 3n-7. It is shown that n-dimensional hypercubeQn(integer n ?6), with at most 3n-7 faulty edges is hamiltonian if the following two fault-tolerant conditions are satisfied:(1) the degree of every vertex is at least two, and(2) there do not exist a forbidden 4-cycle and a forbidden 6-cycle.