Research About K-restricted Edge Connectivity In Graphs

The research on restricted edge connectivity is important in graph theory. Since restricted edge connectivity is a measure of reliability and fault tolerance of networks, restricted edge connectivity has been extensively studied in recent years. We consider a finite, undirected and simple graph G with vertex set V(G) and edge set E(G). For a connected graph G=(V,E), an edge set S C E is a k-restricted edge cut if G-S is disconnected and every component of G-S has at least k vertices. 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).In this paper, we study some problems of restricted edge connectivity in certain graphs. The article is divided into three chapters:In Chapter1, we introduce some basic concepts, terminology and symbols.In Chapter2, we give a sufficient condition for λ5-optimal graphs. The main result is as follows.Let G be a λ5-connected graph with v≥17, δ≥[v-2]-4and λ5(G)≤ξ5(G), and let G’ be any subgraph of G. G satisfies the following three conditions:(i) if G’ is a induced6-cycle or a sticking graph of two triangles connected by an edge, then there is a vertex u of G’ such that d(u)≥[v-2]-2and u is not a sticking point;(ii) if G’is a induced5-cycle or a sticking graph of two triangles, then there is a vertex v of G’ such that d(v)≥[v-2] and v is not a sticking point;(iii) if G’ is a4-cycle, then there is a vertex w of G’ such that d(w)≥[v-2]+4;then G is λ5-optimal.In Chapter3, we give a degree condition for A4-optimal graphs. The main result is as follows.Let G be a A4-connected graph with v≥11and x,y be any two vertices of G. G satisfies the following three conditions:(i) if d(x,y)=4, then max{d(x), d(y)}≥[v-2]-3;(ii) if d(x,y)=3, then max{d(x), d(y)}≥[v-2]-1;(iii) if d(x,y)=2, then max{d(x), d(y)}≥[v-2]+1;then G is A4-optimal.