Sufficient Conditions For Optimality Of K-restricted Edge Connectivity In Graphs

Let S(?)E be a edge cut of G,if G-S is disconnected and every component of G-S has at least k vertices,then edge set S is called a k-restricted edge cut.The k-restricted edge connectivity of G,denoted by?k(G),is defined as the cardinality of a minimum k-restricted edge cut.When k=2,then?2(G)is marked?'(G).Let?k(G)= min{|[X,X]|:|X|=k,G[X]is connected},where X=V(G)\X.A?k-connected graph G is said to be optimally k-restricted edge connected,for short?k-optimal,if?k(G)=?k(G).G is super k-restricted edge connected,for short super-?k,if every minimum k-restricted edge cut of G isolates a component of order exactly k.In 2011,Qin et al.presented some sufficient conditions for graphs to be?'-optimal.In the second chapter,we will improve these results to the situations of?k(k=3,4)-optimality.In 2010,Wang et al.gave some sufficient conditions such that graphs are super-?'.In the third chapter,we will give some sufficient conditions for G being super-?k in graphs.This paper is composed of three chapters.In the first chapter,we simply give some useful basic concepts on graphs which will be used in the paper.In the second chapter,we prove that some sufficient conditions for G is?k(k=3,4)-optimal.The main results are as follows:(1)Let G be a A3-connected graph G of girth g(G)>5.If G contains no such five vertices u1,u2,v1,v2,v3 that distance d(ui,vj)?3(i = 1,2;j=1,2,3),then G is?3-optimal;(2)Let G be a A3-connected graph G of girth g(G)?5.If G contains a vertex u such that distance d(x,y)?2 for all x,y?V(G)\{u},then G is A3-optimal;(3)Let G be a A4-connected graph G of?4(G)??4(G)and girth g(G)?8.If G contains no such six vertices u1,u2,u3,v1,v2,v3 that distance d(ui,vj)?3(i,j = 1,2,3),then G is A4-optimal.In the third chapter,We give some sufficient conditions for G be super-?k.The main results are as follows:Let k?3 be an integer and G be a graph of order v?2k.If |N(u)?N(v)|?k+1 for all pairs u,v of nonadjacent vertices and?k(G)?[v/2]+k,except for some special graphs,then G is super-?k.