Connectivity Of Three Kinds Of Graphs

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 evalu-ated by the parameters of the graphs.There are many parameters that have been introduced to measure the reliability of a network structure.Perhaps,traditional con-nectivity ?(G)of a graph G is the most important one among them.Generally,the larger ?(G)is,the more reliable the network is.However,this criterion has its shortcoming:the further properties of connect-ed components are not depicted.Under this consideration,Harary introduced the concept of conditional connectivity by attaching some conditions on connected com-ponents,Latifi et al.introduced the concept of h-restricted connectivity.Fiol et al.introduced the concept of h-extra connectivity.The classical connectivity ?(G),defined as the minimum cardinality |S| of a vertex-cut S of a graph G.As a natural extension of classiscal connectivity,Given a graph G and a non-negative integer h,the h-extra connectivity ?h(G)of G is the minimum cardinality of a set of the vertices of G,if any,whose deletion disconnect-s G and every remaining component has order more than h;and the h-restricted connectivity ?h(G)of G is the minimum cardinality of a set of the vertices of G,if any,whose deletion disconnects G and every remaining component has the minimum degree of vertex at least h.In this paper,we determined 2-restricted connectivity of folded crossed cube is 4n-4,for n?8.2-restricted connectivity of spined cube is 4n-8,for n?4.And 2-extra connectivity of Johnson graph is 4(n-4),for n?7.