Two Reliability Parameters Of Network Graphs

The conditional connectivity is another method of exploring the network structures out of the vertex-connectivity,which has many applications in the study of fault tolerance of networks.For a connected graph G =(V,E),a subset F(?)V is called an Rk-vertex-cut of G if G-F is disconnected and each vertex in V-F has at least k neighbors in G-F.The cardinality of the minimum Rk-vertex-cut is the Rk-vertex-connectivity of G and is denoted by kk(G).Cayley graphs have a lot of good attributes in the interconnection network,such as vertex transitive,edge transitive,decomposable,high fault tolerance,etc.The study of Cayley graphs has many applications in the field of designing and analyzing networks.Let Sym(n)be the symmetric group on {1,2,...,n}and T be a set of transpositions of Sym(n).Let G(T)denote the graph with vertex set {1,2,...,n} and edge set {ij:(ij)E T}.If G(T)is a wheel graph,then simply denote the Cayley graphs Cay(Sym(n),T)by WGn.The generalized connectivity of a graph G is another natural generalization of the connectivity and can serve for measuring the capability of a network G to connect any k vertices in G.Given a graph G =(V,E)and a subset S(?)V V of at least two vertices,we denote the maximum number r of edge-disjoint trees T1,T2,...,Tr in G by ?G(S)such that V(Ti)?V(Tj)=S for any pair of distinct integers i,j,where 1 ? i,j ? r.For an integer k with 2?k?n,the generalized k-connectivity is defined as ?k(G)=min{KG(S)|S(?)V(G)and |S|?k}.That is,?k(G)is the minimum value of KG(S)overall k-subsets S of vertices.In this paper,we determine the values of ?1 and ?2 for Cayley graphs generated by wheel graphs(denoted by WGn)and prove that ?1(MWn)=4n-6 and ?2(WGn)= 8n-18 when n ?5;we investigate the generalized 3-connectivity of bubble-sort star graphs(denoted by BSn)and show that K3(BSn)= 2n-4 when n ? 3.