Research On Structure Connectivity Of Some Networks

As an extension of connectivity,structure connectivity of graphs was proposed by Lin in 2016.Structure connectivity is used to measure the fault tolerance of networks.For connected graphs G and H,let F be a set of connected subgraphs of G such that each member of F is isomorphic to H（resp.isomorphic to a connected subgraph of H）.Then H-structure connectivity,κ（G;H）（resp.H-substructure connectivity,κ^s（G;H））of G is the size of a smallest set of F such that G-F is disconnected or the singleton.It is easy to find κ^s（G;H）≤κ（G;H）.Stars(K_1,m),paths（P_k） and cycles（C_k） are universal in the network.When a processor fails in a network,virus in the failed processor is likely to spread in a star shape or along a path.Therefore,we pay more attention on structure connectivity of star,path and cycle.In recent years,there are many researches on H-structure connectivity of hypercube,k-ary n-cube,star graph and classical networks,where H is star,path or cycle.For the variants of n-dimensional hypercube Q_n,star structure connectivity of folded hypercube and augmented cube has been solved only for m≤6.The cycle structure connectivity of n-dimensional crossed cube has been solved only for 4-cycle.In this paper,by using the existing g-extra connectivity and large component result,we get some structure connectivity and substructure connectivity of variants of n-dimensional hypercube Qn and augmented k-ary n-cube.We also obtain the structure connectivity and substructure connectivity of DCell and BCDC networks by analyzing their graph structures.This paper consists of six chapters.In Chapter 1,we present basic concepts,terms and notations needed in this article.Then research background and progress of structure connectivity and substructure connectivity are introduced.Finally,we give the main conclusions of this paper.In Chapter 2,we study star structure connectivity and star substructure connectivity of FQn and AQ_n.We extend the original conclusions greatly with the large component method.For n-dimensional folded hypercube FQn,we generalize the number of leaves of stars to n-1.That is,κ(FQ_n;K_1,m)=κ^s(FQn;K_1,m)=「n＋1/2」for n≥7 and 2≤m≤n-1.We have almost completely solved the problem.For n-dimensional augmented cube AQ_n,we generalize the number of leaves of the star to（3n-15）/4 and get the following conclusion:κ(AQ_n;K_1,m)=κ^s(AQ_n;K_1,m)=「n＋1/2」for 4≤m≤（3n-15）/4.In Chapter 3,the star,path structure connectivity and star,path substructure connectivity and cycle substructure connectivity of n-dimensional crossed cube CQ_n have been solved.Thus,we consider cycle structure connectivity of CQ_n.We show some structural properties of a graph induced by neighborhood of any vertex in ndimensional crossed cube CQ_n,first.Then we calculate cycle structure connectivity of CQ_n by using g-extra connectivity.In Chapter 4,we consider the variant CQ_n,n-dimensional folded crossed cube FCQ_n.It is obtained by adding edges to CQ_n.We use large component method to calculate the star,path and cycle structure connectivity of FCQ_n.We get that for 2≤m≤n/2,K_1,m-structure connectivity and K_1,m-substructure connectivity of FCQ_n are 「n＋1/2」.For 3≤k≤n+1.if k is odd（even）,then Pk-structure connectivity,Pk-substructure connectivity and Ck-substructure connectivity of FCQ_n are 「（2（n+1））/（k+1）」（「（2（n+1））/k」）.Furthermore,we calculate the cycle structure connectivity of FCQ_n by dividing the odd length cycle and even length cycle.We prove that for 4≤k≤n+2,C_2k-1-structure connectivity of FCQ_n is 「（n+1）/（k-1）」 and for 6≤k≤n+1 and even k,C2k-structure connectivity of FCQ_n is 「（n+1）/k」+1.In Chapter 5,we study the structural properties of a graph induced by neighborhood of any vertex in AQ_n,k by the definition of augmented k-ary n-cube,AQ_n,k.Combined with the structural properties of AQ_n,k,we study the path structure connectivity and path substructure connectivity of AQ_n,k.Then we get that for n≥3,k≥4,t|（4n-2）,t（?）（2n-1）and t>6,Pt-structure connectivity and Pt-substructure connectivity of AQ_n,k are（4n-2）/t+1.In other cases,Pt-structure connectivity and Ptsubstructure connectivity of AQ_n,k are 「（4n-2）/t」.In Chapter 6,we consider the structure connectivity and substructure connectivity of two data center networks,DCell（Dm,n）and BCDC（Bn）.By analyzing the graph structure,we calculate that for 1≤t≤m+n-2,K₁,t-structure connectivity and K₁,t-substructure connectivity of Dm,n are 「（n-1）/（1+t）」+m.For 3≤s≤n-1,Ks-structure connectivity of Dm,n is 「（n-1）/（1+t）」+m.By applying g-extra connectivity of BCDC network,we get that for n≥5,κ（B_n;H）and κ^s（B_n;H）,where H∈{K₁,t,P_k,C_k|1≤t≤2n-3,6≤k≤2n-1}.