The Structure Fault Tolerance Of Several Classes Of Interconnection Networks

Interconnection networks play an important role in parallel computing and communication systems.By treating the processors as vertices and the direct communication between processors as the edge between two vertices in the interconnection network,the whole entire interconnection network can be viewed as a graph.As the number of vertices in the interconnected network increases,failures are inevitable.Therefore,the fault tolerance of the network is an important issue.Data center networks,(n,k)-star graphs and bubble sort graphs are important networks.In this paper,we study the structure connectivity and substructure connectivity of data center networks,(n,k)-star graphs and bubble sort graphs with respect to star K1,m.The results can provide some new perspectives for measuring the fault tolerant of the three classes of networks.Let H be a connected subgraph of G.The H-structure connectivity of G,denoted by k(G;H),is the cardinality of a minimal set of subgraphs F={H1,H2,...,Ht} in G,such that every Hi∈ F is isomorphic to H,and F’s removal will disconnect G.The H-substructure connectivity of G,denoted by ks(G;H),is the cardinality of a minimal set of subgraphs F={J1,J2,...,Jt} in G,such that every Ji∈F is isomorphic to a connected subgraph of H,and F’s removal will disconnect G.In this paper,we study the structure connectivity and substructure connectivity of three classes of interconnection networks with respect to star K1,m.The structure of the paper is as follows:In the first chapter,we introduce the research background,research status and main concepts involved in the paper.In the second chapter,we introduce the data center network Dk,n and related properties,study the structure connectivity and substructure connectivity of Dk,n with respect to star K1,m,and determine the values of k(Dk,n;K1,m)and ks(Dk,n;K1,m).The specific result is as follows:Let n≥ 3,k≥1 and 1 ≤m≤n-1.Then k(Dk,n;K1,m)=ks(Dk,n;K1,m)=[n-1/m+1]+k.In the third chapter,we introduce the(n,k)-star graph Sn,k and related properties,study the structure connectivity and substructure connectivity of Sn,k with respect to star K1,m,and determine the values of k(Sn,k;K1,m)and ks(Sn,k;K1,m).The specific result is as follows:Let 2 ≤k ≤n-2 and 1 ≤m≤n-2.Then k(Sn,k;K1,m)=ks(Sn,k;K1,m)=[n-k/m+1]+k-1.In the fourth chapter,we introduce the bubble sort graph Bn and related properties,study the structure connectivity and substructure connectivity of Bn with respect to star K1,m,and determine the values of k(Bn;K1,m)and ks(Bn;K1,m).The specific result is as follows:Let n ≥ 4 and 1 ≤m≤n-2.Then k(Bn;K1,m)=ks(Bn;K1,m)=[n-1/2].