The K-restricted Edge-connectivity Of Graphs

Let G be a connected graph.For two disjoint subsets A,B (?) V (G),let [A,B] be the set of edges with one vertex in A,and the other vertex in B. If X (?) V(G), Y=V(G)\X, then S=[X,Y] is called the edge cut of G. Let k be a positive integer. S is called a k-restricted edge cut of G if G-S is disconnected and every component of G-S has at least k vertices.G is called a λk-connected graph if k-restricted edge cut of G exists.The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardiinality of a minimum k-restricted edge cut. Denote ξ(G)=min{|[X,(?)]|: X (?) V(G),|X|=k, G[X] is connected}. G is called a λk-optimal graph if λk(G)=ξk(G).Furthermore,G is called a super-λk graph if every minimum k-restricted edge cut of G isolates one connected subgraph of order k. This paper mainly investigates the optimality of k-restricted edge connectivity. This thesis consists of four chapters.In Chapter1, some useful basic concepts are introduced.In Chapter2, neighborhood conditions for graphs to be λ5-optimal and super-λ5are given.(1) Let G be a λ5-connected graph with order at least21.If N(u)(?)(v)|≥6for all pairs u, v of nonadjacent vertices,and ξ5(G)≤[v-2]+10, then G is λ5-optimal unless G belongs to an especial graph-class.(2) Let G be a λ5-connected graph with order at least21.If|N(u)(?) N(v)|≥6for all pairs u, v of nonadjacent vertices,and ξ5(G)≤[v-2]+11, then G is super-A5.In Chapter3,degree conditions for graphs to be λ5-optimal and super-λ5are given.(1)Let G be a λ5-connected graph with order at least21.For all pairs of x, y∈V(G), if d(x)+d(y)≥2[v-2]+3when d(x,y)=2, d(x)+d(y)≥2[v-2]-1when d(x,y)=3, d(x)+d(y)≥2[v-2]-5when d(x,y)=4, and d(x)+d(y)≥2[v-2]-9when d(x,y)=5,and for any subgraph which is isomorphic to K6, there exists a vertex v satisfying d(v)≥[v-2]+4, then G is λ5-optimal.(2)Let G be a λ5-connected graph with order at least21. For all pairs of x,y∈V(G), if d(x)+d(y)≥2[v-2]+5when d(x,y)=2, d(x)+d(y)≥2[v-2]+1when d(x,y)=3, d(x)+d(y)≥2[v-2]-3when d(x,y)=4, and d(x)+d(y)≥2[v-2]-7when d(x,y)=5,and for any subgraph which is isomorphic to K6, there exists a vertex v satisfying d(v)≥[v-2]+5, then G is super-λ5.Chapter4is devoted to study the relation between graphs of λk-optimal and super-λk. The results are obtained as follows:Let G be a λ5-optimal graph.(1)If δ(G)≥8, then G is λi-optimal for i=1,2,3,4and super-λ, for i=1,2,3. If δ(G)>8, then G is super-λ4.(2)Let G be a triangle-free graph. If δ(G)≥6, then G is λi-optimal for i=1,2,3,4. If6(G)>6, then G is super-λi for i=1,2,3,4.