Component Connectivity And Characterizations Of Optimal Solutions Of Locally Twisted Cubes

Fault tolerance concerns the capability of an interconnection network to trans-mit messages;it is a very important property to study.In general,the network structure is modeled as graphs,and the properties of the network can be evaluat-ed by the parameters of the graphs.There are many parameters that have been introduced to measure the reliability of a network structure.Perhaps,traditional(edge-)connectivity K(G)(λ(G)of a graph G is the most important one among them.Generally,the larger k(G)(λ(G))is,the more reliable the network is.However,this criterion has its shortcoming:the further properties of discon-nected components are not depicted.Under this consideration,Harary introduced the concept of conditional connectivity by attaching some conditions on connected components,Latifi et al.generalized the concept,conditional connectivity by intro-ducing restricted h-connectivity.The concept considered here is slightly different,from theirs.As a natural extension of traditional connectivity,Chartrand and Sampathku-mar introduced independentlyk k-component connectivity ckk(G)and k-omponent edge connectivity cλk(G)of a graph G.Let G be a non-complete graph with ver-tex set V(G)and edge set E(G).A k-component(edge-)cut of G is a set of nodes(edges)whose deletion results in a graph with at least k components.Thek-component(edge-)connectivity ckk(G)(cλk(G))of a graph G is the cardinality of the smallest k-component(edge-)cut of G.A node subset S of(G is called an optimal k-component,(edge-)cut if|S|= cKk(G)(cλk(G))and G—S has exactly k components.In this paper,we determine cKk 1LTQn)for any 1≤k≤n-1,n≥2 and cλk+1(LTQn)for any 1≤k≤2[n/2],n≥7,and we characterize all the corresponding optimal solutions.