| In an interconnected network,the physical connections between its multiprocessor systems can be depicted by a graph,whose nodes in the graph represent the multiprocessor systems in the interconnected network,and edges represent the communication links between the multiprocessor systems.Therefore,we can use the graphs to study the interconnection.In a large-scale interconnected network,it’s unavoidable that processor and physics link will be broken,so the study of network fault tolerance and diagnosis is particularly important.This paper focuses on n-dimensional bubble sort star graphBS_n and complete-transposition graphCT_n.For network topologies,By using their high symmetry and recursion to take the algebraic and combinatorial Methods approach way to study the tolerance ofBS_n andCT_n.At first,this paper introduces some basic knowledge of graphs and networks,several parameters for measuring fault tolerance of interconnection networks and their research status,then studies separately the parameter of tolerance of the two symmetric networks of n-dimensional bubble sort star graphBS_n and complete-transposition graphCT_n.And the main content as follow:(1)Chapter 1:Simply,this chapter introduces the research background and research status of this paper,some basic concepts in graph theory,and the fault tolerance parameters of interconnect networks.(2)Chapter 2:From algebra of view,and takes advantage of recursion ofBS_n to determine the 1,2,3-extra edge connectivity and 1,2-restricted edge connectivity,and cycle(edge)connectivity of the n-dimensional bubble sort star graphBS_n.(3)Chapter 3:First,we determine the 1-restricted edge connectivity of the complete-transposition graph,and then determine the 2-restricted edge connectivity ofCT_n.(4)Chapter 4:We sum up the research content of this paper and puts forward the problems that can be further studied. |
