Study On The Properties Of Local Edge Connectivity Of Graphs And Digraphs

In modern 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. Naturally, in recent years the research into the reliability and fault-tolerability of networks has become a hot research topic at home and abroad. When designing and analyzing the reliability and fault-tolerability of large-scale networks, an important model is to 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 communication between the processors. Assume that all vertices do not fail, and all edges independently fail with equal probability p∈(0,1). So the probability of D being not connected is given by: hereεis the number of edges of D, andλ(D) is the edge connectivity of D. The number of edge cuts of size i is denoted by Ci. Take the probability of D being connected R(G,p)= 1-P(G,p) to measure the reliability of the network. Obviously the smaller P(D,p) is. the better the reliability of networks is.As we know, edge connectivity is a classic parameter in measuring the connectivity of (di-)graphs. But the concept of the classical edge connectivity has some obvious defi-ciencies, when precisely drawing the connectivity properties of (di-)graphs. Firstly, even two (di-)graphs with the same edge connectivity may be considered to have different reli-ability. Secondly, being unable to accurately reflect the extent of damage of the network caused by the damage of gateway. That is. they do not differentiate between the differ-ent types of disconnected (di-)graphs which result from removingλdisconnecting edges. 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, in 1983 Harary proposed the concept of conditional edge connectivity. Esfahanian and Hakimi pro-posed the concept of restricted edge connectivity in 1988. Furthermore, J. Fabrega and M.A.Fiol extended it and proposed the concept of k-restricted edge connectivity in 1996. Fricke and so on proposed the concept of local edge connectivity in 2000. These parameters can reflect deeper connectivity properties of (di-)graphs which classical edge connectivity can not reflect. In this paper, we mainly continue to discuss the properties of local edge connectivity, propose the concept of local k-restricted edge connectivity and discuss its properties on the basis of previous work.In the first chapter, we give a brief introduction to the basic concepts, terminolo-gies and symbols which will be used in this paper. In the meantime, we also give some related research background and some known results. Let D=(V(D),E(D)) be a fi-nite 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. For S,T (?) V(D), let (S,T) be the set of edges with the starting vertex in S, and the ending vertex in T. For X C V(D), D[X] denotes the sub(di-)graph induced by X. Let X=V(D)-X. A digraph with-out any directed cycle of length 2 is called an oriented graph. The degree sequence of D is defined as the nonincreasing sequence of the degrees of the vertices of D. LetΔ+(-)-Δ+(-)(D)= max{d+(-)(v):v∈V(D)},Δ’=Δ’(D)= min {Δ+(D),Δ-(D)}.In order to reflect deeper connectivity properties of (di-)graphs, Fricke and so on proposed the concept of local edge connectivity as follows:Definition1.1 For two vertices u 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 X(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.For the case that (di-)graphs are maximally local-edge-connected, Gao Jingzhen proposed the concept of super local-edge-connectivity of (di-)graphs in order to more deeply draw the reliability of networks.Definition1.2 If aλ(u, v)-cut consists of edges from u or to v. then it is called triv--ial. D is called super local edge connected or simply slec, if every X(u, v)-cut is trivial.In the second chapter, we study on the super local-edge-connectivity of digraphs by using the sum of degrees. So we define the following graphs:Definition 2.1 let M be a digraph of order n and satisfies the following condi--tions :(a)there exists subdivison V(D) = X∪Y, and |X|, |Y|≥2;(b)there exists u∈X, so that |(u, Y)|≥1, and ux∈E(D),|(x, Y)| = 1 for all vertex x∈X\{u};(c)there exists v∈Y, so that |(X,v)|≥1, and yv∈E(D),|(X,y)| = 1 for all vertex y∈Y\{v};(d)d+(x) + d-(y)≥n for all pairs of vertices x,y∈V(D) with d(x,y)≥2.On this basis, we obtain the following best possible result:Theorem 2.2 If D is a digraph of order n such that d+(x) + d- (y)≥n for all pairs of vertices x, y∈V(D) with d(x, y)≥2, then D is super local-edge-connected or D∈M.This theorem, to some extent, improves the result of M.A.Fiol.In the third chapter, we mainly study on the local-edge-connectivity of bipartite digraphs.Firstly, we give degree sequence conditions for bipartite digraphs to be maximally local-edge-connected and super local-edge-connected. And we give examples to explain the best possible of theorem 3.1.2 and 3.1.4(1).Theorem 3.1.2 Let D be a bipartite digraph of order n with degree sequence d1≥d2≥…≥dn(=δ),Δ’ =Δ’(D). Then(1) D is maximally local-edge-connected, ifδ≥[n/4] + 1 orδ≤[n/4] and for some integer k with 1≤k≤2δ: ((2) D is super local-edge-connected, ifδ≥max{3, [n+2/4 + 1} or 3≤δ≤[n+2/4] and for some integer k with 1≤k≤2δ- 1.Theorem 3.1.4 Let D be a bipartite digraph of order n with degree sequence d1≥d2≥…dn(=δ),Δ’ =Δ’(D). Then(1) D is maximally local-edge-connected, ifδ≥[n/4] + 1 orδ≤[n/4] and for some integer k with 1≤k≤2δ;(2) D is super local-edge-connected, ifδ≥max{3, [n+2/4 +1} or 3≤δ≤[n+2/4] and for some integer k with 1≤k≤2δ-1.Theorem 3.1.5 Let D be a bipartite digraph of order n with degree sequence d1>d2>…dn(=δ),Δ’ =Δ’(D). Then(1) D is maximally local-edge-connected, if for some integer k with 1≤k≤δ;(2) D is super local-edge-connected, if 5 > 3 and for some integer k with 1≤k≤δ.Then we study on the super local-edge-connectivity of bipartite digraphs by using Fan-style condition. So we define the following graphsDefinition 3.2.1 Let H1 be complete bipartite digraph K3,3* with V(H1) ={x1,x2, x3}∪{y1,y2,y3}, H2 be complete bipartite digraph A’34 with V(H2) = {ui,u2,u3}∪{v1,v2,v3,v4}. The bipartite digraph H is defined as the disjoint union of H1 and H2 together with the new edges x1v1,x2v2,x2v3,x2v4,y1u1,y2u1 and some edges from H2 to H1 in order to makeδ≥3 and max {d(x), d(y)}≥4 for each pair of vertices x,y∈V’ and each pair of vertices x, y∈V". On this basis, we obtain the following best possible result:Theorem 3.2.4 Let D be a bipartite digraph of order n and minimum degree 5 > 3 with bipartition V’∪V". If max{d(x), d(y)} >n-2/4 for each pair of vertices x,y∈V’ and each pair of vertices x,y∈V", then D is super local-edge-connected or D∈H.In the fourth chapter, we mainly study on the local-edge-connectivity of oriented bipartite graphs, and have the following results:Theorem 4.2 Let D be an oriented bipartite graph of order n with degree sequence d1≥d2≥…≥dn{=δ),Δ’ =Δ’(D). Then(1) D is maximally local-edge-connected, if for some integer k with 1≤k≤2δ;(2) D is super local-edge-connected, ifδ≥2 and for some integer k with 1≤k≤2δ.In the fifth chapter, we propose local k-restricted-edge-connectivity properties of graphs on the basis of k-restricted edge connectivity properties and local edge connec--tivity properties of graphs.Definition 5.1.1 Let G=(V, E) be a. connected graph of order n, the edge cut W is called a A;-restricted (u,v) edge cut of G for u,v∈V(G), if every component of G-W has at least k vertices and u,v belong to different component of G-W. And G is calledλk(u,v)-connected. The k-restricted (u,v) edge connectivity of G is denoted byλk(u, v) = min{|W|:W is the k-restricted (u,v) edge cut of G}, a minimum k-restricted (u,v) edge cut is called aλk(u, v)-cut. G is called localλk-connected, if G isλk(u,v)-cormected for any pair of u,v∈V(G).With regard to the problem of existence of localλk-connected graph, we obtain the following theorem.Theorem 5.1.1 For integer k, let G be a connected graph of order n(≥2k). If G is 2-connected. then G is localλk-connected. hen we propose the concept of localλk-optimal graph which is similar to the concept ofλk-optimal graph.Definition 5.2.1 let G beλk(u,v)-cormec-tod and defineξk(u,v) = min{|(X,X)|,|(Y,Y)|: u∈X(?) V(G),v∈Y (?) V(G),X∩Y=(?),G[X] and G[Y] are connected subgraphs of order k of G }.It is not difficult to see thatλk(u, v)≤ξk(u,v), if G isλk(u,v)-connected for u,v∈V(G).Definition 5.2.2 Let G be a connected graph of order n(≥2k), G is calledλk(u,v)-optirnal or simplyλk(u,v)-opt foru,v∈V"(G), if G isλk(u,v)-connected andλk(u,v) =ξk(u,v). G is called localλk-optimal or simply localλk-opt, if G isλk(u,v)-optimal for any pair of u, v∈V(G).We obtain neighborhood condition for graphs to be localλk-optimal:Theorem 5.2.4 For integer k, let G be a localλk-connected graph of order n(≥2k). If |N(x)∩N(y)|≥2k-1 for all pairs of x,y of nonadjacent vertices and |N(x)nN(y)|≥2k for all pairs of x, y of nonadjacent vertices with the property that x or y lies on a triangle, then G is localλk-optimal.