Properties Of The Local Edge Connectivity Of Digraphs

With the development of social economy ,science and technology,the relationshipbetween man and networks becomes more and more closely.Naturally,the research aboutthe reliability and fault-tolerability of networks is very active at home and abroad.Aswe know,edge connectivity plays an important role in the connectivity of graph.But theconcept of the classical edge connectivity has some obvious deficiencies.Firstly,even twographs with the same edge connectivity may be considered to have diferent reliabil-ity.Secondly,they do not diferentiate between the diferent types of disconnected graphswhich result from removingκdisconnecting vertices orλdisconnecting edges.Thirdly,itis tacitly assumed that all elements in any subset of G can potentially fail at the sametime .Consequently,to compensate for these shortcomings,it seems natural to generalizethe notion of classical edge connectivity.Since Harary[1]proposed the concept of condi-tional edge connectivity in 1983,after the development in more than twenty years,thecontents in conditional edge connectivity become richer and more specific, including su-per edge connectivity,extra edge connectivity,restricted edge connectivity, and so on.Andsince Fricke proposed the concept of local edge connectivity in 2000,after the developmentin more than ten years,the contents in local edge connectivity become richer and morespecific,including maximally local edge connectivity and super local edge connectivity,and so on.The design and analysis of reliability and fault-tolerability of large-scale networkstypically involve some types of graph theoretic model,one important model is a graphsuch as:Assume that all vertices of G = (V, E) are perfectly reliable and all edges fail in-dependently,with the same probabilityρ∈(0, 1).The number of edge cuts of size i is denoted by Ni(G).Then the probability R(G, p) of G being connectedness is given byhereεis the number of edges of G,the edge connectivity of G,denoted byλ(G),is definedas the cardinality of a minimum edge cut.In general,it is difcult to determine Ni(G) of agraph[2].The restricted edge connectivity was proposed by Esfahanian and Hakimi[3].Thisconcept can reflect more connected properties of graphs that classical concept can notreflect.Furthermore,Q.L.Li and Q.Li[4]proposed the concept of super restricted edge con-nectivity.In this paper,we mainly continue to discuss the properties of edge connectivityon the basis of previous work.In the first chapter,we give a brief introduction about the basic concepts,terminologies and symbols which will be used in this paper.In the meantime,we aslo give somerelated research background and some known results.Let D = (V (D), E(D)) be a digraph,if u is a vertex of D,then we denote the sets ofout-neighbors and in-neighbors of u by N+(u) and N (u) respectively. Furthermore,thedegree d(u) of a vertex u in a digraph D is defined as the minimum value of its out-degreed+(u) and its in-degree d (u).The minimum out-degree,minimum in-degree and mini-mum degree of a digraph D are denoted byδ+(D),δ(D) andδ(D) =min{δ+(D),δ(D)}.Let is =min{max{d+(u), u∈V (D)},max{d (u), u∈V (D)}}.The degree sequenceof D is defined as the nonincreasing sequence of degrees of the vertices of D.For two setsS, T V (D),let (S, T ) be the set of edges from S to T .Let D be a connected digraph of order n,the local-edge-connectivity of two ver-tices u and v isλ(u, v) =min{|(X, Y )| : u∈X V (D)\{v}, Y = V (D)\X},the edgecut (X, Y ) is called aλ(u, v)-cut if it is the minimum cut satisfied the above condi-tion.Obviouslyλ(u, v)≤min{d+(u), d (v)}. A digraph D is called maximally local-edge-connected(mlec)[5]ifλ(u, v) =min{d+(u), d (v)} for every u, v∈V (D).Furthermore,D iscalled super-local-edge-connected(slec),if everyλ(u, v)-cut is from u to Y or from X tov.For G = V (V, E), u, v∈V (G),the edge cut W with u∈W and v∈G W is calledk-restricted (u, v) cut if every component of G W has at least k vertices.A connectedgraph is calledλ(u, v)-connected if k-restricted (u, v) cut exists.The k-restricted (u, v)edge connectivity of G is denoted byλk(u, v) =min{|W | : W is k-restricted (u, v) cut of G}, W is called aλk(u, v)-cut if it is the minimum cut satisfied the above condition. Letξk(u, v) =min{|(X, X)|, |(Y, Y )| : u∈X V (G), v∈Y V (G), X∩Y = , G[X], G[Y ]are connected subgraphs of order k}.Obviously,λk(u, v)≤ξk(u, v).G is calledλk(u, v)-optimal(λk(u, v)-opt) if G isλk(u, v)-connected andλk(u, v) =ξk(u, v) for u, v∈V (G).IfG isλk(u, v)-optimal for every u, v∈V (G),then G is called localλk-optimal(localλk-opt).The above concepts can be found in [6].In the second chapter,we give some sufcient conditions for a (di)graph to be maxi-mally local-edge-connected and super local-edge-connected by using degree,and have thefollowing results:Definition 2.1.1 Smis a digraph class satisfied the following conditions:(1) There exists subdivision V (D) = X∪Y, |X| = |Y | = m≥2;(2) D[X], D[Y ]=～Km ;(3) There exists u∈X, v∈Y, such that |(x, Y )| = |(X, y)| = 1 for arbitraryx∈X\{u}, y∈Y \{v}.(4)δ(D) = m.Definition 2.1.2 Sm0is a graph class satisfied the following conditions:(1) There exists subdivision V (G) = X∪Y, |X| = |Y | = m≥2;(2) G[X], G[Y ]=～Km;(3) There exists u∈X, v∈Y, such that |(x, Y )| = |(X, y)| = 1 for arbitraryx∈X\{u}, y∈Y \{v} and |(u, Y )| = |(X, v)|≥1.Theorem 2.1.3 If D is a digraph of order n and minimum degreeδsuch thatn≤2δ,then either D is super local-edge-connected or D∈Sn2.Corollary 2.1.1 If G is a graph of order n and minimum degreeδsuch thatn≤2δ,then either G is super local-edge-connected or G∈S0n.2Theorem 2.2.2 Let D is a digraph of order n and = (D) with degree sequence d1≥d2≥...≥dn(=δ).(1)Ifδ≥[n/2] orδ≤[n/2]—1 and for some integer k with 2≤k≤δ,then D is maximally local-edge-connected.(2)Ifδ≥[n/2]+1 orδ≤[n/2] and for some integer k with 1≤k≤δ,then D is super local-edge-connected.Theorem 2.2.4 Let D is a(di)graph of order n and△’=△’(D)with degree sequence d1≥d2≥...≥dn(=δ).Ifδ≥[n/2]+1 orδ≤[n/2] and for some integer k with 1≤k≤δ,then D is super local-edge-connected.Theorem 2.3.2 Let D is an orientde graph of order n and△’=△’(D)with degree sequence d1≥d2≥...≥dn(=δ).Ifδ≥[n+1/4] orδ≤[n+1/4] -1 and for some integer k with 1≤k≤2δ,then D is super local-edge-connected.In the third chapter,we mainly study the sufficient conditions for bipartite digraphs to be maximally local-edge-connected and super-local-edge-connected by using neighbor-hood conditions, and have the following results:Theorem 3.1.3 Let D is a bipartite digraph of order n,if the minimum degreeδ≥3 and min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥n+3/4 for each paie of same part vertices x,y,then D is maximally local-edge-connected.Theorem 3.2.2 Let D is a bipartite digraph of order n,ifδ≥4 and min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}＞n/4+1 for each pair of same part vertices z,y,then D is super local-edge-connected .In the fourth chapter,we mainly study the localλk-optimality and local super-λkedge connectivity of graphs, and have the following results:Definition 4.2.1 Let G be connected graph of order n(≥2k),for u, v∈V (G), Gisλk(u, v)-connected.If everyλk(u, v)-cut isolates a connected subgraph contained u oforder k or isolates a connected subgraph contained v of order k,then G is called super-λk(u, v) graph.If for arbitrary u, v∈V (G), G is super-λk(u, v) graph,then G is calledlocal super-λkgraph.Theorem 4.1.2 If G is a localλ2-connected graph of order n satisfying the fol-lowing three conditions,then G is localλ2-optimal.Definition S2(k) is the graph class satisfied the following conditions:(1) there exists subdivision V (G) = X∪Y, |X|, |Y |≥k + 1;(2) G[X], G[Y ] are complete graphs;(3) there exists x0∈X, y0∈Y ,such that |N(x0)∩Y |≥k, |N(y0)∩X|≥k;(4) |N(x)∩Y | = |N(y)∩X| = k,for arbitrary x∈X\{x0}, y∈Y \{y0}.Theorem 4.2.3 Let k be a positive integer and let G be a localλk-connectedgraph with order at least 2k.If |N(x)∩N(y)|≥2k + 2,for all pairs x, y of nonadjacentvertices,then either G is local super-λkor G∈S2(k).