The Properties Of Edge Connectivity And Vertex Connectivity Of Digraphs And Oriented Graphs

In recent years, with the rapid development of large scale integrated circuit, mi-croelectronic technique and large-scale networks, people make a more and more high requirments for the topological structure of the network. Graph theory and its exten-sive application in many fields draw more and more attention from mathamatics field and-other scientific field. The reliability and fault-tolerability of networks are widely concerned. The connectivity analysis in graph theory provides an important theoretical support for this research.When designing and analyzing multiprocessors interconnection network, usually in-volves some type of graph theoretic model, using vertexes and edges of graph instead of nodes and links of network in order to constitute the interconnected network topology. 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 represent direct com-munication 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 connected is given by: To calculate P(D,p) exactly, one need to calculate all the coefficients Ci(D). But in 1983, Provan and Ball proved that it is NP-hard to determine all these coefficients. Colbour made further explanations for that.But the concept of the classical edge connectivity or vertex connectivity has some obvious deficiencies when precisely drawing the connectivity 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 k 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, since 1983 Harary proposed the concept of con-ditional edge connectivity, after 20 years of development, the edge connectivity involved increasingly rich content and specific, including super edge connectivity, maximally lo-cal edge connectivity and super local edge connectivity, etc. Similarly, as to the vertex connectivity, the concepts of maximally connectivity and maximally 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 existing results,, some basic concepts and terminology symbol involved in this paper.In the second chapter, we mainly study on the local-edge-connectivity of oriented graphs, we give low degree conditions for oriented graphs to be maximally local-edge-connected and super local-edge-connected.Theorem 2.1.3 Let D be an oriented graph of order n, △’=△’(D), with degree sequence d1≥d2≥…≥dn(=δ). Then:(1) If δ≥[(n-1)/4],)or δ ≤[(n-2)/4] and∑ dn+1-i≥k(n-1-k)+1+max{0, △’+k-2δ-2,2△’+2k-n-2}, for some integer k with 1≤ k≤2δ+1,then D is maximally local-edge-connected.(2) If δ≥[(n-1)/4],)or δ ≤[(n-2)/4] and ∑ dn+1-i≥k(n-1-k)+1+max{0, △’+k-2δ-2,2△’+2k-n-2}, for some integer k with 1≤k≤2δ, then D is super local-edge-connected.Then,we give oriented bipartite graphs are maximally local-edge-connectivity of about sum-degree conditions.Theorem 2.2.4 Let D be an oriented bipartite graph of order n,the minimum degree δ≥2.Then D is super local-edge-connected,If for any pair of vertices u and v in the same part we have d+(u)+d+(v)>n/2-3/2 and d-(u)+d-(v)>n/2-3/2.In the third chapter,we mainly study on the local-edge-connectivity of oriented graphs depending on the clique number.First,we present oriented graphs are maximally local-edge-connected depending on the clique number.Theorem 3.1.3 Let D be an digraph of order n,the clique number of D,ω(D)≤p, △’=△’(D),with degree sequence d1≥d2≥…≥dn(=δ).If n≤2[(pδ)/(p-1)]1 or n≥2[(pδ)/(p-1)] and for some integer k with 1≤k≤[δ/(p-1)],then D is maximally local-edge-connected.Theorem 3.1.4 Let D be an digraph of order n,the clique number of D,ω(D)≤p, △’=△’(D).minimum degree δ,with degree sequence d1≥d2≥…≥dn(=δ).If n≤2[(pδ)/(p-1)]-1 or n≥2[(pδ)/(p-1)] and for some integer k with 1≤k≤[(pδ)/(p-1)],then D is maximally local-edge-connected.Then we present oriented graphs are super local-edge-connected depending on the clique number.Theorem 3.2.4 Let D be an digraph of order n,the clique number of D ω(D)≤p. △’=△’(D)；minimmum degree δ≥3,with degree sequence d1≥d2≥…≥dn(=δ).If n≤2[(pδ)/(p-1)]-3,or n≥2[(pδ)/(p-1)]-2 and for some integer k with 1≤k≤[(pδ)/(p-1)]-1,then D is super local-edge-connected.Theorem 3.2.5 Let D be an digraph of order n,the clique number of D,ω(D)≤p, △’=△’(D),minimum degree δ≥2,with degree sequence d1≥d2≥…≥dn(=δ).If n≤2[(2pδ)/(p-1)]-3,or n≥2[(2pδ)/(p-1)]-2 and for some integer k with 1≤k≤[(2pδ)/(p-1)]-1, then D is super local-edge-connected.In the fourth chapter, we mainly study on the maximally edge-connectivity of di-graphs with the inverse degree conditions.Theorem 4.1.2 Let D be a strongly connected digraph with n≥ 2,minimum degree δ.If δ≥[(n-1)/2],)or δ ≤[(n-2)/2] and then D is maximally edge-connected.Theorem 4.2.2 Let D be a strongly connected triangle-free digraph,the minimum degreeδ. If δ≥[(n+1)/4],)or δ ≤[n/4] and 则 D is maximally edge-connected.In the fifth chapter,we get the sufficient conditions for p-diamond free graph and K2,3-free graph to be local-connected.Theorem 5.2 Let p≥2 be an integer and G be a connected p-diamond-free graph,u,v ∈V(G).Then G is super local-connected.If define r=min{d(u), d(v)}-δ(≥0).Theorem 5.5 Let G be a connected K2,3-free graph with minimum degree S(G)≥ 2. If n(G)≤3δ(G)-3, then G is maximally local-connected.