Edge-fault-tolerant Diameter For Two Family Interconnection Networks

With the rapid development of science and technology, computer systems need to deal with more and more information and data. It is proved that graph theory is the most fundamental and powerful mathematical tool to design and analyse interconnection networks. An interconnection network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. Then some complex network problems can be studied by mathematical methods. The diameter of graph can be used as a characterization of network communications. So to examine the differences of graph diameter is a method for calculating the transmission delay of networks. In chapter2, we will give some systematic explanation about basic concept and the correlation between graph and network. On the other hand, since vertex faults and/or edge faults may occur to networks, it is significant to design and analyse faulty networks. The fault-tolerant diameter and the edge-fault-tolerant diameter, which given in chapter3, are two important measurements for reliability and efficiency of an interconnection network. Many popular networks, such as hypercube, twisted-cube, Mobius cube, k-ary n-cubes, Recursive circulant graphs et al., can be expanded into higher dimensional networks by connecting some lower dimensional networks. In chapter4, we give two important interconnection networks, which are the expansion of such graph models. Let x and y be arbitrary two distinct vertices in fault networks. We will obtain the bounds of edge-fault-tolerant diameter of these two family interconnection networks by constructing an (x,y)-path with required length.