SUN Gaoxing,MENG Jixiang

(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

Abstract: The interconnection networks are generally modeled by a connected graph G,and the connectivity of Gis an important parameter for reliability and fault tolerance of the network.A connected graph G=(V,E)is maximally connected(or optimal-κ for short)if its connectivity attains its minimum degree.We de fine a optimal-κ graph G to be m-optimal-κ if G?Sis still optimal-κ for any vertex subset S? V(G)with|S|≤ m.The maximum integer of such m,denoted by Oκ(G),is said to be the vertex fault tolerance of Gwith respect to the optimal-κ property.In this paper,we get the upper and lower bounds of the vertex fault tolerance for optimal-κ property of G(G0,G1;M)networks,from which we determine the exact values of Oκ(G)for some well-known networks.

Key words:interconnection network;maximally connected;vertex fault tolerance

0 Introduction

For the interconnection network topology,it is usually represented by a graphG,while vertices represent processors and edges represent links between processors.And the connectivity is an important classic measurement for the reliability and fault tolerance of a network.In general,the larger the connectivity is,the more reliable the corresponding network is.It is well-known that κ(G)≤ δ(G).Hence we call a connected graphGwith κ(G)= δ(G)maximally connected(or optimal-κ for short).For more results related to the maximally connected graphs,we cite[1]for references.

There has been several papers investigating how many faulty edges can be tolerated such that the remaining graph is still super-λk.The edge fault tolerance of a super-λkgraph with respect to super-λkproperty,denoted by ρk(G),is de fined as the maximum integermfor whichG?Sremains super-λkfor any subsetS?E(G)with|S|≤m.In[4],Hong et al.studied the bounds whenk=1,and presented more re fined bounds for some special classes of graphs.In[5],Cheng and Hsieh studied the bounds of ρk(G)fork≥3.Some works about the edge fault tolerance of graphs with respect to maximally-λ property are onging.In[6],Hong et al.showed the vertex fault tolerance of graphs with respect to optimal-κ property.

It is an important issue to consider faulty networks,since faults of some processors and communication links in a large-scale system are inevitable.Wang and Lu[7]discussed the edge fault tolerance ρ1(G)of three families of interconnection networks.Hong and Xu[8]showed the bounds of ρ2(G),and determined the exact values of ρ1(G)for some well-known networks.Someone has discussed the edge fault tolerance of two families of interconnection networks with respect to maximally-λ property.Some related results about the restricted connectivity of some networks can be found in[9-12].

The family ofG(G0,G1;M)networks we will discuss was first proposed by Chartrand and Harary[13],who called them permutation graphs.In this paper,we show the vertex fault tolerance ofG(G0,G1;M)with respect to optimal-κ property.The conception of which is as follows.

Definition 1An optimal-κ graphGism-maximally connected(orm-optimal-κ for short)ifG?Sis still optimal-κ for any vertex subsetS?V(G)with|S|≤m.

Definition 2The vertex fault tolerance of a optimal-κ graph with respect to the optimal-κ property,denoted byOκ(G),is the integermsuch thatGism-optimal-κ but notm+1-optimal-κ.

In Section 2 of this paper,we are devoted to prove our main results.Before proving the main results,we introduce some related notations and two crucial lemmas in Section 1.

1 Preliminaries

We follow Bondy and Murty[14]for terminology and notation not de fined here and only consider finite simple undirected graphs.LetG=(V,E)be a connected graph.We say a graphGistrivialifGhas only one vertex.Thedegreeof a vertexv,denoted bydG(v),is the number of vertices incident to it.Let δ(G)=min{dG(v)|v∈V(G)},andnδ(G)be the number of vertices with minimum degree.For a vertex subsetXofV(G),G[X]is the subgraph ofGinduced byXandis the complement ofX.An vertex subsetS?V(G)is called a vertex cut ifG?Sis disconnected or trivial.The connectivity,denoted by κ(G),is the minimum cardinality through all vertex cuts ofG.For each vertexv∈V(G),theneighborhood NG(v)ofvis de fined as the set of all vertices adjacent tov,anddG(v)=|NG(v)|is the degree ofv.For a vertex setX?V(G),denote byNG(X)the set of all vertices inadjacent to some vertex inX,that is,NG(X)= ∪v∈XNG(v)X.When the graph under consideration is obvious,we omit the subscriptGand used(v),δ,N(X)etc.

fig 1 Graph G(G0,G1;M)

LetG0andG1be two graphs with the same number of vertices,thenG(G0,G1;M)is a new graph with vertex setV(G)=V(G0)∪V(G1)and edge setE(G)=E(G0)∪E(G1)∪M,whereMis an arbitrary perfect matching betweenG0andG1(see fig 1).We observe that the hypercubes are constructed in this way,so are many variations of the hypercubes,such as the twisted cubesTQn[15],the locally twisted cubesLTQn[16],the crossed cubesCQn[17],and the M¨obius cubesMQn[18]etc.

Lemma 1[6]A connected graphGis optimal-κ if and only if|N(X)|≥ δ(G)holds for any non-empty vertex setX?V(G)withN(X)∪XV(G).

Lemma 2[6]For a vertex setS?V(G),supposeXis a nonempty proper vertex subset ofV(G)such that

(a)X?V(G)?S,NG?S(X)<δ(G?S),NG?S(X)∪XV(G?S),and

(b)under the condition of(a),|X|is as small as possible.

Then

(i)G[X]is connected;

(ii)for any componentCofG?N(X)with|V(C)|<|X|,V(C)?S;

(iii)|A|≥2;

(iv)for anyy∈NG?S(X),|NG?S(y)∩X|≥2.

Theorem 1[6]LetGbe an optimal-κ graph with minimum degree δ and 1-extra connectivity κ1.Supposenδ≥ δ.Then min{κ1?δ,δ?1}≤Oκ(G)≤δ?1.

2 Main results

In this section,we will study the upper and lower bounds onOκ(G)for the familyG(G0,G1;M)of networks.The following result presents an upper bound ofOκ(G)for general optimal-κ graphsG.

Lemma 3For any optimal-κ graphG,Oκ(G)≤ δ(G)?1.

In fact,letv∈V(G)be a vertex withd(v)=δ(G),andNG(v)be the neighbourhood ofv.ThenG?NG(v)is disconnected and thus is not optimal-κ.By the Definition ofOκ(G),we haveOκ(G)≤ δ(G)?1.

Theorem 2LetGi=(Vi,Ei)be a connected graph of ordernwith δi= δ(Gi)= κ(Gi)= κi≥ 2,i=0,1.LetG=G(G0,G1;M)and=min{δ0,δ1},thenGis optimal-κ with κ(G)=δ(G)=+1.

ProofBy the Definition ofG=G(G0,G1;M),we know that δ(G)=+1.According to Lemma 1,we will show that|N(X)|≥ δ(G)holds for any non-empty vertex setX?V(G)withN(X)∪XV(G).We discuss two cases.

Case 1X?V(G0)orX?V(G1).

Without loss of generality,we supposeX?V(G0).Consider thatN(X)∪V(G0)and,clearly,X?V(G0).

In this case,|NG0(X)|≥δ0whenNG0(X)is a vertex cut ofG0,and|NG0(X)|=n?|X|whenNG0(X)is not a vertex cut ofG0.We have

Case 2

LetX∩V(G0)=X0andX∩V(G1)=X1.

ClaimEitherNG0(X0)∪X0V(G0)orNG1(X1)∪X1V(G1).

IfNG0(X0)∪X0=V(G0)andNG1(X1)∪X1=V(G1),thenNG(X)∪X=V(G).Hence we supposeNG0(X0)∪X0V(G0),that is to sayNG0(X0)is a vertex cut ofG0.Notice thatNG(X)=NG0(X0)∪NG1(X1)∪(NG1(X0)X1)∪(NG0(X1)X0),we have

The proof is complete.

Now,we are ready to give an upper and lower bound onOκ(G)forG=G(G0,G1;M)as follows.

Theorem 3LetGi=(Vi,Ei)be a connected graph of ordernwith δi= δ(Gi)= κ(Gi)= κi≥ 2,containing no triangles,i=0,1.LetG=G(G0,G1;M)and=min{δ0,δ1},supposenδ(G)≥,then?1≤Oκ(G)≤.

ProofAccording to Lemma 3 and Theorem 2,we know thatOκ(G)≤(+1)?1=.

Case 1X?V(G0)orX?V(G1).

Without loss of generality,we supposeX?V(G0).Consider thatand,clearly,X?V(G0).

Case 1.1NG0(X)∪X=V(G0).

In this case,|NG0(X)|=n?|X|and|NG1(X)|=|X|,then we have

Sincenδ(G)≥,and|S|≤?1,there exists at least one vertex with degree δ(G)inGwhich do not contain inS.Thus δ(G?S)≤ δ(G),and we have|NG?S(X)|≥ δ(G?S).

Case 1.2NG0(X)∪X,V(G0).

Case 1.2.1|X|=1.

In this case,Xcontains only one vertexv,then|NG?S(X)|=dG?S(v)≥δ(G?S).

Case 1.2.2|X|≥2.

IfXis a independent subset ofV(G),then|NG?S(X)|≥min{dG?S(v)|v∈X}≥δ(G?S).In addition,letuvbe an edge ofG[X].Due to our assumptionGicontains no triangle and the construction ofG(G0,G1;M),Gcontains no triangles,and|NG0(u)|+|NG0(v)|≥2.Thus we have|NG0(X)|=|∪v∈XNG0(v)X|≥2?|X|,thus

Case 2X∩V(G0),?andX∩V(G1),?.

With the same discussion as Case 2 in above theorem,we supposeNG0(X0)∪X0,V(G0).

Case 2.1NG1(X1)∪X1,V(G1).

In this case,|NG0(X0)|≥ δ0,and|NG1(X1)|≥δ1.Hence

Case 2.2NG1(X1)∪X1=V(G1)withn?|X1|≥δ1.

In this case,|NG0(X0)|≥δ0,and|NG1(X1)|=min{δ1,n?|X1|}=δ1.Hence

Case 2.3NG1(X1)∪X1=V(G1)withn?|X1|<δ1.

Now,we consider the cardinality ofX0.Either|X0|=1 orX0is a independent subset ofV(G0),we have|NG?S(X)|≥dG?S(v)?1+|NG1?S(X1)|≥ δ(G?S),wherev∈V(G0).Besides,there exists at least an edge inX0,throughout a similar argument with Case 1.2,we have|NG0(X0)|≥2?|X0|.And|NG1(X1)|=n?|X1|.Hence

If|X0|+|X1|≤n,we have|NG?S(X)|≥+1≥δ(G?S).If|X0|+|X1|>n,we suppose,to the contrary,|NG?S(X)|<δ(G?S)for a nonempty proper vertexsubset ofV(G)withX∪NG?S(X),V(G?S).According to Lemma 2,X∪NG?S(X)=V(G?S)if each componentCofG?N(X)has cardinality less than|X|,a contradiction.Otherwise,there exists at least one componentDwith|D|≥|X|>n,we have|V(G)|>|X|+|D|>2n,a contradiction.

The proof is complete.

Remark 1We known??1≥?1 whenn≥2,in this case,we can improve the lower bound of Theorem 3 frommin{?1,n??1}to?1.Notice that|V(G)|≥|NG(u)|+|NG(v)|≥2δ(G),whereuvis an arbitrary edge of a connected graphGcontaining no triangles.

Remark 2LetGbe a cycle with just one pendent vertexv,and then δ(G?v)=2> δ(G).That is to say the minimum degree do not always decrease with vertex fault,which is different with the edge version.nδ(G)≥δ(G)is just necessary to make sure δ(G?S)≤δ(G),and there is a example graph showing the condition can not be omitted in[7].

Corollary 1LetGi=(Vi,Ei)be a connected δi-regular graph of ordernwith δi= δ(Gi)= κ(Gi)= κi≥ 2,containing no triangles,i=0,1.LetG=G(G0,G1;M),=min{δ0,δ1},thenOκ(G)=.

Consider that the conditionnδ(G)≥in Theorem 3 is only used to deduce δ(G?S)≤δ(G).For the graphGdescribed in above corollary,nδ(G)≥+1 always holds.Therefore the lower bound for regular or bipartite semi-regular version can be optimized tomin{,n?}=,since δ(G?S)<δ(G)for any non-empty vertex setS?V(G).

Since graphG(G0,G1;M)is a generalization of the hypercubesQn,twisted cubesTQn,locally twisted cubesLTQn,crossed cubesCQnandM¨obiuscubesMQn,we have the following corollary.

Corollary 2LetGn∈{Qn,TQn,LTQn,CQn,MQn}.Ifn≥3,thenOκ(Gn)=n?1.

ProofGncan be viewed as the graphG(Gn?1,Gn?1;M)corresponding to some matchingM.And δ(Gn?1)= δ=n?1,|V(Gn?1)|=2n?1.Whenn≥ 3,we con firm 2n?1≥ 2n?2.

Then by Corollary 1,it follows that