Local-edge-connectivity Of Graphs And Digraphs

The edge connectivity problem of graphs and some other graph theories are allfrom the study of the big network design and reliability analysis. In our living, theedge connectivity problem has a big application, and with the development of thefield some scholars presented and studied a few edge connectivity problems withdiferent restrictions.A processor interconnection network or a communications network is typicallymodeled by （undirected or directed） graph, in which the node set corresponds toprocessors, and the edge set corresponds to communication links. When studyingthis kind of model, one often considers whose nodes never fail but links（edges） failindependently of each other, with the same probabilityρ∈（0, 1）. One fundamentalconsideration in the design of such networks is overally reliablity, which can usuallybe measured by the edge-connectivity of the graphs. Let G = （V （G）, E（G）） be anetwork model, the number of its edge cuts of size i is denoted by C_i（G）, then theprobability （or reliability） R（G,ρ） of G being connectedness is given byhereεis the number of edges of G, the edge connectivity of G, denoted byλ（G）, isdefined as the cardinality of a minimum edge cut. Clearly, the smaller R（G,ρ）is, the more reliable the network is. To determine the reliabity, one need todetermine all the coefcients C_i（G）. But unforfunately, it is N P hard to de-termine all these coefcients^[1,2,3]. Whenρis sufciently small, the maximum value of R（G,ρ） can be obtained by maximizingλ（G） first and then minimizingC_λ, C_λ+1, , Cεsequentially[4]. So edge connectivity plays an important role in theconnectivity of graph.But the concept of the classical edge connectivity has some obvious deficien-cies. Firstly, even two graphs with the same edge connectivity may be consideredto have diferent reliability. Secondly, it is tacitly assumed that all elements in anysubset of G can potentially fail at the same time; Thirdly, they do not diferentiatebetween the diferent types of disconnected graphs which result from removingλdisconnecting edges. For the case that some connectivity parameters are proposedto investigate the reliability, which including maximally edge-connectivity, super-edge-connectivity and local-edge-connectivity. In this paper, we mainly continue todiscuss the propeties of local-edge-connectivity on the basis of previous work.In this paper, we consider finite graphs and digraphs without loops and mul-tiple edges. In the first chapter, we give a brief introduction about the basicconcepts, terminologies and symbols which will be used in this paper. In themeantime, we also give some related research background and some known re-sults. For any digraph D = （V, E）, the vertex set is denoted by V （D） and theedge set by E（D）, and let n（G） = |D| denote the order of a digraph D. ForX（?）V （D）,let D[X ] be the subgraph induced by（?） ,（?） = V （G） X . Let′be′（D） = min{max{d⁺（v） : v∈V （D）}, max{d^- （v） : v∈V （D）}}. For A, B V ,let [A, B] be the set of edges with one vertex in A, and the other vertex in B. Thedistance d（u, v） = d_D（u, v） from u to v in a digraph D is the length of a shortestdirected path from u to v in D. The distance d（X, Y ） = d_D（X, Y ） from a ver-tex set X to a vertex set Y in D is given by d_D（X, Y ） = min_x∈X,y∈Yd_D（x, y） anddm（D） = max_u,v∈V （D）d_D（u, v） stands for the diameter of D. A digraph withoutany directed cycle of length 2 is called an oriented graph. A digraph D is k edge-connected if for any set S of at most k 1 edges the subgraph D S is stronglyconnected. The edge connectivityλ=λ（D） is defined as the largest value of k such that D is k edge-connected.Because ofλ（D）≤δ（D）, we call a digraph D maximally edge-connected ifλ（D） =δ（D）. A digraph D is super-edge-connected or superλ, if every minimumedge-cut is trivial, that means, that every minimum edge-cut consists of edges ad-jacent to or from a vertex of minimum degree. The local-edge-connectivity of twovertices u and v in a digraph D is denoted byλ（u, v） = min{|（X, Y ）| : u∈X V （D）\{v}, Y = V （D）\X }. A minimum edge-cut （X, Y ） is called aλ（u, v） cut.Clearly,λ（u, v）≤min{d⁺（u）, d^- （v）}. We call a digraph D maximally local-edge-connected whenλ（u, v） = min{d⁺（u）, d^- （v）} for all pairs u and v of vertices inD. If for any pair of vertices u, v∈V （D）, everyλ（u, v） consists of the edgesadjacent from the vertex u , or adjacent to the vertex v, the digraph D is call to besuper-local-edge-connected. Clearly, if a digraph D is super-local-edge-connected,the D is superλand maximally local-edge-connected. For our purpose, we willdeal with a graph G by considering the digraph D（G） which obtained from G byreplacing each edge uv∈E（G） by the two directed edges （u, v） and （v, u）. Thereforthe graph can be seen as a special digraph.In the second chaper, we mainly study some sufcient conditions for graphsand bipartite graphs to be super-local -edge-connected by using diameter and thelength of its longest cycle, we have the following results:Theorem 2.1.3 Let G be a connected graph of diameter at most two. IfG contains no cycles of length greater than 4, then G is either super-local-edge-connected or G∈H₁H₂.where the definition of H_i（i = 1, 2） can be found in the text.Theorem 2.1.4 Let G be a connected graph of diameter at most two, andorder n（G）≥6.If G contains no cycles of length greater than 3, then G is super-local-edge-connected. Theorem 2.2.4 Let G be a connected bipartite graph of diameter at most two,and order n（G）≥6.If G contains no cycles of length greater than 4,then G is super-local-edge-connected.In the third chaper,we will give sufficient conditions for a bipartite digraph to be super-local-edge-connected by using the degree,and have the following results:Theorem 3.4 Let D be a bipartite digraph of order n and minimum de-greeδ≥2.If d+（u）+d+（v）>n/2+1 and d-（u）+d-（v）>n/2+1 for each pair u and v of vertices in the same part of D,then G is super-local-edge-connected.Theorem 3.4’ Let D be a bipartite digraph of order n and minimum de-greeδ≥2.If d+（u）+d+（v）≥（2n-5）/4 and d-（u）+d-（v）≥（2n+5）/4,for each pair u and v of vertices in the same part of D,then G is super-local-edge-connected.Sufficient conditions for oriented graphs to be maximally edge-connected and super-edge-connected have been given by several autors.In the forth chaper,using the well-known Theorem of Turan,we present degree sequence conditions for super-local-edge-connected oriented graphs depending on the clique number.Firstly,we present the higher end of the degree sequence conditions for a ori-ented to be super-local-edge-connected.Theorem 4.5 Let G be an oriented graph,clique numberω（D）≤p,and de-gree sequence d1≥d2≥…≥dn（=δ≥2）,△’=△’（D）.If n≤2[2pδ/（p-1）]-3 or if n≥2[2pδ/（p-1）]-2≥4p-2 and for some k with 1≤k≤[2δ/（p-1）]-1,then G is super-local-edge-connected. Theorem 4.6 Let G be an oriented graph,clique numberω（D）≤p,and degree sequenced1≥d2≥…≥dn（=δ≥2）,△’=△’（D）.If n≤2[2pδ/（p-1）]-3 or if n≥2[2pδ/（p-1）]-2 and for some k with 1≤k≤2δ,then G is super-local-edge-connected.Secondly,we present the lower end of the degree sequence conditions for a oriented to be super-local-edge-connected.Theorem 4.7 Let G be an oriented graph,clique numberω（D）≤p,and degree sequence d1≥d2≥…≥dn（=δ≥2）,△’=△’（D）.If n≤2[2pδ/（p-1）]-3 or if n≥2[2pδ/（p-1）]-2 and for some k with 1≤k≤[2δ/（p-1）]-1,then G is super-local-edge-connected.Theorem 4.8 Let G be an oriented graph,clique numberω（D）≤p,and degree sequence d1≥d2≥…≥dn（=δ≥2）,△’=△’（D）.If n≤2[2pδ/（p-1）]-3 or if n≥2[2pδ/（p-1）]-2 and for some k with 1≤k≤2δ,then G is super-local-edge-connected.