A Kind Of Conditional Vertex Connectivity Of Star Graphs

The interconnection of a set of processors can be represented by a simplegraph G = (V,E), where each vertex (also node) u∈V represents a processor,and each edge (also link) (u,v)∈E represents a link between the vertices uand v. The connectivityκ(G) of G is an important measure for reliability ofthe network[1]. In general, the largerκ(G) is, the more reliable the network is.However,κ(G) is a worst case measure and thus underestimates the resilienceof the network. To overcome such shortcoming, Harary introduced the conceptof conditional connectivity by putting some requirements on the components ofG - F[2]. Theκ2-vertex connectivity is one in this trend. Let G = (V,E) be afinite graph without loops and parallel edges.κ~2(G) = min{|F| |each vertex inG - F has at least two neighbors in G - F, and G - F is not connected}.Let X be a group and S be a subset of X. The Cayley digraph Cay(X,S) is adigraph with vertex set X and arc set {(g,gs) | g∈X,s∈S}. Denote byΣn thegroup of all permutations on {1,···,n}. An n-dimensional star graph Sn is theCayley graph Cay(Σn,S) with S = {(1i) | 1 < i n}. The n-dimensional stargraph is an important network topology since it has high symmetry (vertex/edgetransitivity), high fault tolerance (n?2), smaller degree (n-1), smaller diameter( 23(n - 1) ) and hierarchical structure (allowing recursive constructions) etc[3].The main result in this paper isκ2(Sn) = 6(n - 3).This dissertation is organized as follows. In Chapter 1, we introduce brieflythe background of this study and some terminologies. In Chapter 2 and Chapter3, we give some properties of star graphs and prove the main result of this paper.