Topology and fault tolerance of interconnection networks

Interconnection networks is an enormous field which holds a very important position in both theory and practice. From a practical point of view, networks should be fast and reliable as much as possible. The performance of most network systems is limited by computational power as well as by interconnection capability. To improve the interconnection capability, we need to discover good network topology. Combining with more powerful hardware and more efficient algorithms, the performance of networks can be improved. The topology of networks is usually studied in ternis of graph theory. At the abstract level, interconnection networks are nothing but graphs, undirected or directed. Several comnion desirable features of networks such as high throughput, fast message exchange, fault tolerance and low complexity etc. correspond to properties of the underlying graphs of networks, including low degree, large number of nodes, high connectivity etc. Considering three parameters, namely, the number of vertices in a graph, degree and diameter, if we optimize each one of these three parameters in turn while holding the other two fixed, we obtain three optimization problems, namely, the degree/diameter problem, the order/degree problem and the order/diameter problem for both directed and undirected case. We shall discuss these three problems and show that certain monotonicity relationships hold among the parameters and among the problems. In this thesis we also deal with the issue of fault tolerance of networks. We investigate the connectivity of a particular type of network structure called (k;g)-cages. In 1997. Fu et al. conjectured that all (k;g)-cages are k-connected. This conjecture implies that all (k;g)-cages are k-edge-connected as well. We present new resuts with respect to edge-connectivity and combined with previous results from Balbuena et al. we completely solve the conjecture with respect to edge-connectivity. Additionally, we provide a positive contribution to the conjecture with respect to vertex-connectivity.