Fault-Tolerant Analysis Of Some Networks

Interconnection networks play an important role in parallel computing and com-munication systems. Fault tolerance of the interconnection networks is an ability to remain some properties in the presence of failures, and is also a crucial factor to evalu-ate the performance of the interconnection networks. In this thesis, using graph theory as a tool, we study the interconnection networks’ability to remain three properties:the existence of many-to-many disjoint long paths, minimum degree of the connected com-ponents, sub-network embedding in the connected components. In the study, we take full advantage of the equivalence of the decompositions in the highly symmetrical net-work from different dimensionality, explore an effective method for the fault tolerance analysis of networks, solve several unresolved problems.In the first chapter, we introduce the research background of faulty-tolerant analy-sis in the interconnection networks and the main graph theory concepts and terminolo-gies will be used in this paper.In the second chapter, we study the many-to-many k disjoint fault-free paths in the hypercube Qn, In the conditional vertex faulty assumption, we prove that if the number of fault vertex/does not exceed2n-2k-3, S and T are two k-vertex sets in different parities of Qn, there is k fault-free disjoint paths connecting S to T, and containing at least2n-2f vertices. This result improves some known results in a sense.In the third, fourth chapters, we focus on analyze the fault-tolerant performance of the hypercube-like networks and the star graphs. Theoretically speaking, the hypercube-like networks and the star graphs are very attractive alternative for the hypercubes in terms of various desirable properties of an interconnection structure. In chapter3, we determine the high order restricted edge connectivity and the high order embedding re-stricted edge connectivity of the hypercube-like networks. In vertex case, we determine the high order restricted vertex connectivity and the high order embedding restricted ver- tex connectivity of some special hypercube-like networks, such as Hypercube, Mobius cube, Crossed cube. In chapter4, we determine the high order restricted vertex (edge) connectivity and the high order embedding restricted vertex (edge) connectivity of the star graph. In particular, our result about the restricted vertex connectivity of the star graph give an affirmative answer to a conjecture proposed by peer scholars.In the fifth, sixth chapters, we mainly study the restricted connectivity in the gen-eralized star networks and the exchanged hypercube. The generalized star networks is a generalization of star graphs, with more flexible numbers of vertex, received much attention in recent years. As a variation of the hypercube, the exchanged hypercube constructed by systematically deleting some edges in the hypercube, keep numerous desirable properties of the hypercube and reduce the interconnection complexity. In Chapters5and6, we determine the high order restricted vertex (edge) connectivity of the generalized star and the exchanged hypercube, respectively.