The Optimality Of K Restricted Edge Connectivity In Graphs

Let G=(V, E) be an undirected, simple and connected graph. An edge set S C E 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. If the k restricted edge cut of G exists, then G is λk-connected. Furthermore, the k restricted edge connectivity of G, denoted by λk(G), is defined to be the cardinality of a minimum k restricted edge cut. The k restricted edge connectivity, as a generalization of edge connectivity, is an important measure of fault-tolerance for interconnection networks. Let ξk(G)=min{|[X,(?)]|:X (?) V,|X|=k,G[X] is connected}. A connected graph G is called an optimal k restricted edge connected (or λk-optimal for short) graph if λk(G)=ξk(G). In this paper, we mainly study some sufficient conditions of the optimal k restricted edge connectivity of graphs (k=4,5). The paper is divided into two chapters.In the first chapter, the notation and terminology which will be used in this paper are introduced.In the second chapter, some sufficient conditions for graphs to be A4-optimal and ξ5-optimal are given. The main results are as follows.(1) Let G be a A4-connected graph of order n (n≥11). If|N(u)(?)N(v)|≥6for all pairs u, v of nonadjacent vertices, and G[N(u)(?) N(v)] contains at least16edges, then G is λ4-optimal.(2) Let G be a λ5-connected graph. S=[X, Y] is an edge-cut in G. If|N(u)(?) N(v)|≥8for all pairs u, v of nonadjacent vertices, and|X4|≤1, then G is A4-optimal.(3) Let G be a λ5-connected graph of order n (n≥52). If|N(u)(?) N(v)|≥8for all pairs u, v of nonadjacent vertices, and ξ5(G)≤2n+3, then G is λ5-optimal.(4) Let G be a A5-connected graph. If|N(u)(?) N(v)|≥8for all pairs u, v of nonadjacent vertices and for each triangle T there exists at least one vortex v∈V(T) such that d(v)≥[n-2]+4, then G is λ5-optimal.