Edge-Connectivity Of Graphs And Digraphs

Graphs are often as models for the multiprocessor interconnection networks. One fundamental consideration in the design of such networks is overall reliability, which can usually be measured by the connectivity or the edge-connectivity of the graphs. If G be an undircted, simple and connected gragh of minimum degreeδ, edge-connectivityλ. thenλ<δ. A graph G is called maximally edge-connected ifλ=δ. A graph is called super-edge-connected if every minimum edge-cut consists of edges incident to a vetex of minimum degree. The super-edge-connectivity provides a more accurate index of fault-tolerance of networks than maximally edge-connectivity.In Chapter 1, after a short introduction to the used basic notation and terminology on graphs, we give in Section 1.2 some concepts and results on the edge connectivity.In Chapter 2 we mainly study lower bounds on the edge-connectivity of digraphs. New lower bounds on the edge-connectivity of digraphs, bipartite digraphs and oriented graphs are given.A graph without any directed cycle of length 2 is called an oriented graph. Sufficientconditions for oriented graphs to be maximally edge-connected and super-edge-connected have been given by several authors. However, closely realated conditions for maximally edge-connected and super-edge-connected graphs and oriented graphs depending on the clique number were received little attention until recently. In Chapter3 some degree sequence conditions for graphs as well as oriented graphs depending on the clique number to be maximally edge-connected and super-edge-connected are given as follows:(1) Let G be a graph of order n, clique numberω(G)≤p, minimum degreeδ(≥4(p-1)/p),edge-connectivityλ, and degree sequence d₁≥d₂≥…≥d_n. If n≤2(?)p^δ/2(p-1)」-1 or if n≥2(?)p^δ/p-1」and sum from i=1 to k(d_i+d_n+i-δ≥k(n-2k+2k(p-1)/p)+2δ+1 forsome integer k with 1≤k≤δ,then G is super-edge-connected.(2) Let D be an oriented graph of order n, clique numberω(D)≤p,minimumdegreeδ, edge-connectivityλ, and degree sequence d₁≥d₂≥…≥d_n. If n≤2(?)2p^δ/p-1」-1 or if n≥2(?)2p^δ/p-1」and sum from i=1 to k(d_i+d_n+i-2δ-1≥k(n-2k+k(p-1)/p)+2δ-1 forsome integer k with 1≤k≤2δ+1,thenλ=δ.(3) Let D be an oriented graph of order n, clique numberω(D)≤p, minimumdegreeδ(≥2(p-1)/p),edge-connectivityλ, and degree sequence d₁≥d2≥…≥d_n.Ifn≤2(?)p^δ/p-1」-1 or if n≥2(?)2p^δ/p-1」and sum from i=1 to k d_i+sum from i=1 to (2p-1)k d_n+1-i≥k(p-1)(n-p)+2δ+1for some integer k with 1≤k≤(?)δ/p-1」,then G is super-edge-connected. In Chapter 4, we study super-edge-connectivity of graphs with diameter 2. Fiol showed in 1992 that there are 3 sufficient conditions for a digraph to be super-edge-connected (a) diam(D) = 2, and D contains no complete symmetric digraph K_δ^* with all its vertices of out-degreeδor all its vertices of in-degreeδ; (b) d⁺(x) + d^-(y)≥nfor all pairs x,y of vertices such that d(x,y)≥2, and D is different from 2K_n/2^*; (c)d⁺ (x) + d^-(y)≥n + 1 for all pairs x, y of vertices such that d(x, y)≥2. We provedthat (1°) the condition (a) is not a necessary condition for a digraph with diameter 2 to be super-edge-connected: (2°) (c) (?)(b) (?)(a), (a)(?) (b) (?) (c).