K-restricted Edge Connectivity Of Graphs

For a connected graph G=(V,E), we denote by[A,B] the set of edges of G with one end in A and the other end in B.When Y=V\X, the edge set [X,Y] is called the edge cut of G associated with X.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. If G has a k-restricted edge cut, then G is a λk(G)-connected graph.The k-restricted edge connectivity of G,denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G)=min{|[X,(?)]|:|X|=k, G[X] is connected}. G is λk-optimal if λk(G)=ξk(G). In2004, Volkmann et al. gave some sufficient conditions on neighborhood such that graphs are λ’-optimal. In this paper, we will improve these results to the situations of λk-optimality in graphs. In this paper, we will give some sufficient conditions for G being λk-optimal.This paper is composed of four 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 introduce the development of restricted edge connectivity.In the third chapter, we prove that G is λk-connected in the neighborhood condition|N(u)∩N(v)|≥k for each pair u, v of non-adjacent vertices satisfies. Furthermore, we give a neighborhood condition for G is λk-optimal. The main results are as follows:(1) Let k be a positiVe integer and let G be a graph of order at least2k. If each pair u, v of non-adjacent vertices satisfies n(u)∩N(v)|≥k, then G is λk-connected and λk(G)≤ξk(G).(2) Letk≥3be an integer and let G be a graph of order at least2k. If each pair u, v of non-adjacent vertices satisfies|N(u)∩N(v)|≥k and ξk [v-2]+k, then G is λk-optimal, where G (?) W(see chapter3).(3) Let k≥4be an integer and let G be a graph of order at least2k. If each pair u, v of non-adjacent vertices satisfies|N(u)∩N(v)|≥k and ξk≤[v-2]+K, then G is λk-optimal.In the fourth chapter, We give some sufficient conditions for G be λkk-optimal. The main results are as follows:(1) Let k≥2be an integer and let G be a λk-connected graph of order at least2k, and let S=[X, Y] be a λk-cut of G such that|X|≥k+1and|Y|≥k+1. If|N(u)∩N(v)|≥k+1 for all pairs u, v of non-adjacent vertices such that neither u nor v lies on a triangle,and|N(u)∩N(v)|≥2k-1for all pairs u, v of non-adjacent vertices such that u or v lies on a triangle, then there exists a (k-1)-path in G[X] and G[Y], respectively.(2) Let k≥2be an integer and let G be a graph of order at least2k. If|N(u)∩N(v)|≥k+1for all pairs u, v of non-adjacent vertices such that neither u nor v lies on a triangle,and|N(u)∩(v)|≥2k-1for all pairs u, v of non-adjacent vertices such that u or v lies on a triangle,then G is λk-optimlal.