| With the rapid development of society, 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 in recent years it 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)[1]. 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[2] made further explanations for that. There is a similar dis-cussion 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[5] proposed the concept of conditional edge connectivity, after30years 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 A-cut of D. Obviously, X(D)≤δ(D). A (di-)graph is called to be maximally edge connected if X(D)=δ(D). If every λ-cut of D only consists of all edges from or to a vertex, then D is called super edge connected or simply super-A. For two vertices u and v in a (di-)graph D, the local-edge-connectivity is denoted by X(u, v)=min{|(X, Y)｜:u∈X C V(D)\{v}, Y=V(D)\X}, a minimum (X,Y) is called A(u,v)-cut of D. Obviously, X(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[6], when λ(u, v)=min{d+(u),d-(v)} for all pairs u and v of vertices in D. If every X(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 κ(G)=min{|S|:S c 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 κ(G)=n(G)-1. Obviously, κ(G)≤δ(G). G is called to be maximally connected if κ(G)=δ(G). A κ-cut is said to be trivial if it only consists of all neighbors of some vertex. A graph G is called to be super-κ, if all its K-cuts are trivial. The local connectivity κ(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, κ(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 κ(u, v)=min{d(u), d(v)} for all pairs u and v of vertices in G.For u of vertices in G, the set of external(internal) neighbors is denoted by N+(-)(u). In the second chapter, we present in this paper neighborhood conditions for maximally local-edge-connected and super local-edge-connected bipartite oriented graphs:Theorem2.1.4Let D be a bipartite oriented graph of order n, and δ(D)≥3. If and 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 oriented graph of order n, and δ(D)>4. If and for any pairs x and y of vertices in the same part, then D is super local-edge-connected.Then, we make a discussion about the degree sequence conditions for super local-edge-connected bipartite oriented graphs, getting the following conclusion:Theorem2.2.5Let D be a bipartite oriented graph, the degree sequence is d1> d2≥...≥dn{=δ≥2), if δ≥｜n+3/8|or δ<|n+2/8|and for some integer with1≤k≤4δ-1,then D is super local-edge-connected.In the third chapter,at first,we present in this paper degree sequence conditions for super edge-connected bipartite oriented graphs:Theorem3.1.2Let D be a bipartite oriented graph,the degree sequence is d1≥d2≥…≥dn(=δ≥2),if δ≥[n+3/8] or δ≤[n+2/8] and for some integer k with1≤k≤4δ-1,then D is super edge-connected.For e=uv of edges in D,let N+(e)=(N+(u)∪N+(v))\{u,v),ξ+=min{N+(e): e∈E(D)}.Similarly denote N-(e),ξ-.And define the minimum restricted arc-degree of DξN=ξN(D)=min{ξ+,ξ-).We firstly present a sufficient condition for super edge connected digraphs with the minimum restricted arc-degree,and show that the condition is best possible.Theorem3.2.4Let D be an incomplete digraph of order佗,the degree sequence is d1≥d2≥…≥dn(=δ).If∈ξN≥[n/2]+δ-1or ξN≥[n/2]+δ-1and for some integer k with2≤k≤ξN-δ+2,then D is super edge conneeted.Then we present the edge neighborhood conditions for super edge connected di-graphs.Theorem3.2.7Let D be a strongly connected digraph of order n with edge con-nectivity λ and minimum degree δ.If for each edge e=uv with max{d+(d+(v),d+(v)}≤[n/2]-1,and if for each edge e=uu with max(d-(u),d-(u)}≤[n/2]-1,then D is super edge connected or D∈H*.At last,we present the degree sequence conditions for super edge connected graphs depending on the clique number, and show that the conditions are best possible.Theorem3.3.4Let the clique number of G u(G)≤p,degree sequence is d1≥d2≥...≥dn(=δ≥3).(1)Assume that p≠δ and p-1+δ.If n≤2|pδ/p-1|-1or n≥2|pδ/p-1|≥2p and for some integer κ with1≤κ≤｜δ/p-1|,then G is super edge connected.(2)Assume that p=δor p-1|δ.If n≤2|pδ/p-1|-3or n≥2|pδ/p-1|-2and for κ=1when p=δ,or if n≥2|pδ/p-1|-2≥2p-2and for κ=1when p-1=δ,or for some integer κ with1≤κ≤δ/p-1-1when p-1|δ and p-1≠δ,then G is super edge connected.Cartesian product is an important and common method in constructing large-scale networks,which can remain many properties of small grids unchanged.In the fourth chapter,we mainly study on the super local connectivity of Cartesian product of two regular graphs,and have the following results.Theorem4.2If d1regular graph G1and d2-regular graph G2are both super local connected,and d1,d2≥2,then G1×C2is super local connected. |
PDF Full Text Request