| Recent years, the relationship between people’s daily life, work, study and internet networks of multiprocessor becomes increasingly close,the reliability and fault-tolerability of networks are widely concerned, and has become one of the hot research topic at home and abroad. The connectivity analysis in graph theory provides an important theoretical support for this research.When designing and analyzing the reliability and fault-tolerability of large-scale networks, we usually abstract the topological structure of the network into a (di-)graph D=(V,E). Then vertices of D express processors, and edges connected vertices repre-sent direct communication between the processors (directed edge represents that there is only one-way link between the processors). Assume that all vertices do not fail, and all edges independently fail with equal probability p∈(0,1). The number of edges of D is denoted by m,λ(D) is the edge connectivity of D, and the number of edge cuts of size i is denoted by Ci(D).So the probability of D being not connected is given by And the probability of D being connected R(G,p)=1-P(G,p) can be used to measure the reliability of the network. Obviously the smaller P(D,p) is, the better the reliability of networks is. However, for a digraph, it is a NP-hard problem that to make sure all of the coefficient. Colbour made further explanations for that. There is a similar discussion assuming that all edges do not fail, and all vertices independently fail with equal probability p∈(0,1).Edge connectivity and vertex connectivity are two important parameters in reflect-ing the connectivity of (di-)graphs. But the concept of the classical edge connectivity or vertex connectivity has some obvious deficiencies when precisely drawing the con-nectivity properties of (di-)graphs. Firstly, even two (di-)graphs with the same edge connectivity or vertex connectivity may have different reliability. Secondly, being unable to distinguish between the different types of disconnected (di-)graphs which result from removing λ disconnecting edges or κ disconnecting vertices. That is, the model is unable to accurately reflect the extent of damage of the network caused by the damage gateway. Thirdly, it is tacitly assumed that all elements in any subset of D may potentially fail at the same time. Consequently, to compensate for these shortcomings, since1983Harary proposed the concept of conditional edge connectivity, after20years of development, the edge connectivity involved increasingly rich content and specific, including super edge connectivity, maximally local edge connectivity and super local edge connectivity, etc. Similarly, as to the vertex connectivity, the concepts of maximally connectivity and max-imally local connectivity occured. The parameters can more deeply depict the properties of edge connectivity and vertex connectivity of (di-)graphs. In this paper, we mainly continue to discuss the properties of super edge connectivity of (di-)graphs and super local vertex connectivity of graphs, on the basis of previous work.In the first chapter, we mainly introduced the research background, some exist-ing results, some basic concepts and terminology symbol involved in this paper. Let D=(V(D), E(D)) be a finite and simple (di-)graph, where V(D) is the vertex set and E(D) is the edge set. And let n=|V(D)|denote the order of D. A digraph without any directed cycle of length2is called an oriented graph.The edge connectivity of a (di-)graph is defined as λ(D)=min{|(X,Y)|:θ≠X C V(D),Y=V(D)\X), and a minimum (X,Y)is called λ-cut of D. Obviously, λ(D)≤δ(D). A (di-)graph is called to be maximally edge connected if λ(D)=δ(D). If every A-cut of D only consists of all edges from or to a vertex, then D is called super edge connected or simply super-λ. For two vertices v and v in a (di-)graph D, the local-edge-connectivity is denoted by λ(u,v)=min{|(X,Y)|:u∈X(?)V(D)\{v},Y=V(D)\X], a minimum (X,Y) is called λ(u,v)-cut of D. Obviously, λ(u,v)≥min{d+(u), d-(v)} for all pairs u and v of vertices in D. We call a (di-)graph D maximally local-edge-connected or simply mlec, when λ(u, v)=min{d+(u),d-(v)} for all pairs u and v of vertices in D. If every λ(u, v)-cut consists of edges from u or to v, then D is called super local edge connected or simply slec. Obviously, if D is super local edge connected, it must be super-λ, and maximally local-edge-connected.The connectivity of an incomplete graph G is defined as k(G)=min{|S|:0≠Sc V(G), G-S is not connected}, and a minimum S is called k-cut. The connectivity of a complete graph G is defined as k(G)=n(G)-1. Obviously, k(G)≤δ(G). G is called to be maximally connected if k(G)=δ(G). A k-cut is said to be trivial if it only consists of all neighbors of some vertex. A graph G is called to be super-k, if all its k-cuts are trivial. The local connectivity k(u, v) of two vertices u and v in a graph G is the maxi-mum number of internally disjoint u-v paths in G. Clearly, k(u, v)<min{d(u),d(v)} for all pairs u and v of vertices in G. We call a graph G maximally local connected if k(u, v)=min{d(u), d(v)} for all pairs u and v of vertices in G.In the second chapter, we present in this paper conditions for maximally local-edge-connected and super local-edge-connected bipartite oriented graphs:Theorem2.1.4let D be a bipartite digraph of order n, and S(D)>2If max{d(x), d(y)}≥n/4, for any pairs x and y of vertices in the same part, then D is maximally local-edge-connected.Theorem2.2.3let D be a bipartite digraph of order n, and δ(D)≥3If max{<d(x), d{y)}≥n/4for any pairs x and y of vertices in the same part, then D is super local-edge-connected.In the third chapter,we first present degree sequence conditions for maximally local-edge-connected bipartite oriented graphsTheorem3.1.3Let D be a bipartite oriented graphs whose degree sequence is d1≥d2≥…≥dn{=δ≥1), if δ≥[n+1/8], or δ≤[n/8],and1≤k≤45for an integer k. Then D is maximally local-edge-connected.Then we present the edge-neighborhood conditions for some special graphs to be maximally local-edge-connectedDefinition3.2.1Let H*be a digraph D of order n with edge-cut S, S,satisfied the follow conditions:(1) If|S|≤|S|, and E[S0]=0, exist x∈S1let|(x,S0)|≥1.(2)If|S|≥|S|, and E[S0]=0,and exist y∈S1let|(S0,y)|≥1.Theorem3.2.3Let D be a strongly connected bipartite digraph,if max{d+(u), d+(v)}<[n/2]-1for all edges e=uv satisfying max.{d-(u), d-(v)}≤[n/2]-1, for all edges e=uv satisfying then D is maximally local-edge-connected or D G H*.At last we present the distance maximal set conditions for some special graphs to be maximally local-edge-connectedDefinition3.3.1Let H**be a bipartite digraph D satisfied:(1) If|X|≤|Y|, we get|X’0|=0, and exist x G X’1, let|{x,X"0)|≥1; or|X"0|=0, and exist x G X"1, let|(x,X’0)|≥1;(2) If|Y|≤|X|, we get|Y’0|=0, and exist y G Y’1, let|(Y"0,y)|≥1; or|y"0|=0, and exist y∈Y"1, let|(Y’0,y)|≥1;Theorem3.3.5Let D be a connected bipartite digraph.If for all (4,4)-distant max-imal pairs of vertex sets S, T, there exists a point u in D[S∪T] let dD[X]+(u)=0or v∈Y, let dD[Y]-(v)=0satisfying dD(u)≥△’, then D is maximally local-edge-connected or D∈H**Theorem3.3.6Let D be a connected bipartite digraph.If for all (4,4)-distant maximal pairs of vertex setsS, T, there exists an isolated edge st in D[S∪T] satisfying dD(s),dD(t)≥△’, then D is maximally local-edge-connected or D∈H**.For u of vertices in G, the set of external(internal) neighbors is denoted by N+(-)(u).In the fourth chapter, we present in this paper neighborhood conditions for maxi-mally local-edge-connected and super local-edge-connected bipartite digraphs:Definition4.1.1Let H\be complete bipartite digraph K2,2*with vertex set V(H1)={x1,x2}∪{y1,y2}, Let H2be complete bipartite digraphs K2,2*wtih vertex set V(H2)={u1,u2}∪{v1,v2}.Let H1*be a digraph obtained by combine H1,H2,then add edges y2u1,x2v1and some edges from H2to H1satisfies δ≥2and min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥3, for each pair of vertices x,y.。。Let {u}=x2{v}=v1,we get|(X, Y)|-λ(u, v)=2<3=min{d+(u),d-(v)}. so,H1*is not maximally local-edge-connected.Definition4.1.2Let H1be complete bipartite digraph K2,2*with vertex set V(H1)={x1,x2}∪{y1,y2}, Let H2be complete bipartite digraphs K2,3*with vertex setV(H2)={u1,u2}∪{v1,x2,x3}.Let H2*be a digraph obtained by combine H1,H2,then add edges x2v1,x2v2,y2u1and some edges from H2to H1,satisfies5≥2and min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥3, for each pair of vertices x,y.Let {u}=x2,{v}=v1,we get|(X,Y)|=X(u,v)=2<3=min{d+(u),d-(v)}. so H2*is not maximally local-edge-connected.Theorem4.1.2let D be a bipartite digraph of order n, and δ(D)≥2If min{|N+(x)|∪|N+(y)|,|N-(x)|∪|N-(y)|}≥n+3/4, for any pairs x and y of vertices in the same part, then D is maximally local-edge-connected or D∈H1*or H2*.Definition4.2.1Let H1be complete bipartite digraph K2,3*with vertex set V(H1)={x1,x2)∪{y1,y2,y3}, Let H2be complete bipartite digraphs K2,3*with vertex set V(H2)={u1,u2}∪{v1,v2,v3}.Let H3*be a digraph obtained by combine H1,H2,then add edges x2v1,y1u1,y2v2,y3u3and some edges from H2to H1, satisfies δ≥2and min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥3, for each pair of vertices x, y.Let {u}=x2,{v}=v1,we get|(X,Y)|=λ(u,v)=2<3=min{d6(u),d-(v)}. so H3*is not super local-edge-connected.Definition4.2.2Let H1be complete bipartite digraph K2,3*with vertex set V(H1)={x1, x2}∪{y1,y2,y3}, Let H2be complete bipartite digraphs K3,3*with vertex set V(H2)={u1,u2,u3}∪{v1,v2,v3}.Let H4*be a digraph obtained by combine H1,H2,then add edges x2v1,x2v2,y1v1,y2v2,y3v3and some edges from H2to H1, satisfies δ≥3and min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥3, for each pair of vertices x,y.Let {u}=x2,{v}=v1,we get|(X,Y)|=λ(u,v)=2<3=min{d+(u),d-(v)}. so H4*is not super local-edge-xnnected.Theorem4.2.2let D be a bipartite digraph of order n, and δ(D)≥3If min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥n/4+1, for any pairs x and y of vertices in the same part, then D is super local-edge-connected orD∈H3*or H4*... |
PDF Full Text Request