Sufficient Conditions For Maximally Arc-connected Digraphs

The multiprocessor interconnection networks are conveniently modeled by graphs or digraphs, in which the vertex set corresponds to processors and the edge (arc) set cor-responds to communication links. One fundament consideration in the design of such networks is reliability (fault tolerance), which can usually be measured by the edge-connectivity (arc-connectivity) of the graphs (digraphs). The larger the edge-connectivity (arc-connectivity) is, the more reliable the network is. We call the graphs with optimal edge-connectivity (arc-connectivity) maximally edge-connected graphs (arc-connected di-graphs). The article is divided into four chapters, in which, the arc-connectivity of digraphs and the restricted edge-connectivity of graphs are studied.In Chapter 1, we give basic notation and terminologie on graphs.In Chapter 2, we introduce the concept of isolated arcs and give some sufficient conditions for strongly connected digraphs and strongly connected bipartite digraphs to be maximally arc-connected. The main results are as follows:(1) Let D be a strongly connected digraph with arc-connectivityλand minimum degreeδ. If for all 3-distance maximal pairs of vertex sets X, Y (?) V, there exists an isolated arc in D[X∪Y], thenλ=δ.(2) Let D be a strongly connected bipartite digraph with arc-connectivityλand minimum degreeδ. If for all (4,4)-distance maximal pairs of vertex sets X, Y(?) V, there exists an isolated arc in D[X U Y], thenλ=δ.(3) Let D be a strongly connected digraph, and let S=[X, X] be a minimum arc-cut of D, where X=V\X. If there exists a u∈X such that |N+(x)∩X|≥1 for any x∈X\{u}, or if there exists a u∈X such that |N-{y)∩X|≥1 for any y∈X\{u}, thenλ=δ.In Chapter 3, we study the arc-connectivity of a class of strong product digraphs. The main results are as follows:(1) Let Di be a nontrivial strongly connected digraph with order ni, size mi, minimum degreeδi and arc-connectivityλi, for i=1,2. Ifδi+=δi, thenλ(D1 (?) D2)≤min{λ1(n2+m2),λ2(n1+m1),δ1+δ2+δ1δ2}.(2) Let D2 be a nontrivial strongly connected digraph with order n2, size m2, mini-mum degreeδ2 and arc-connectivityλ2.Ifδ2+=δ2-=δ2, thenλ(C2 (?) D2)=min{4λ2,1+ 2δ2}.Futhermore, ifδ2≤2λ2-1, then C2 (?) D2 is maximally arc-connected. In Chapter 4, we give some sufficient conditions for the p-q-restricted vertex-connectivityκp,q(G) to be a lower bound on the p-p-restricted edge-connectivityλp,p(G). The main result is as follows:(1) Let G be aκp,q-connected andλp,p-connected graph, (q≤p). If there exists a minimum p-p-edge-cut S=[X, X] and a connected subgraph G1 of order q of G[X] such that N(G1)∩X=φ, thenκp,q(G)≤λp,p(G).(2) Let G be aκp,q-connected andλp,p-connected graph, (q≤p). If there are a minimum p-p-edge-cut S=[X, X] and a p-q-vertex-cut T such that①for any x∈X, N(x)∩X≠φ,②G-T has a component of order at least p, whose vertex set is contained by X, thenκp,q(G)≤λp,p(G).