Optimality And Superiority Of K-Restricted Edge Connectivity Of Graphs

With the rapid development of social economy, science and technology, the relation-ship between mankind and networks becomes more and more close, the research about the reliability and fault-tolerability of networks has attracted increasing attention, which has been one of the focal points of worldwide attention. As we know, edge-connectivity of graphs plays an important role in the connectedness of graphs. But the classical concept of the edge-connectivity has three obvious deficiencies. Firstly, even two graphs, with the same connectivity may be considered to have different reliability. Secondly, they do not differentiate between the different types of disconnected graphs which result from re-movingκdisconnecting vertices orλdisconnecting edges. Thirdly, it is tacitly assumed that all elements in any subset of G can potentially fail at the time. Consequently, to compensate for these shortcomings, it seems natural to generlize the notion of classical edge-connectivity. Since Harary[1] proposed the concept of conditional connectivity in 1983, the contents-in conditional connectivity become more rich and specific.When we design and analysis the reliability of large-scale networks, it typically involves some measure standards and types of graph-theoretic models. There are many different theoretical problems that arise from the different measure standards and types of graph models. One important model is a network of such as:A graph G = (V,E), assuming that the nodes do not fail, meanwhile the edges fail independently and with the same probability p∈(0,1). Ifεis the total number of edges in G, Ch is the number of edge-cuts of size h, the probability P(G,p) that G is disconnected can be expressed as therefore, the reliability of G is 1-P(G,p). Clearly, the smaller.P(G,p) is, the more reliable the network is. Naturally, in order to determine P(G,p) for a given graph G and p, we need to determine all the coefficients Ch However, J.S.Provan and M.O.Ball[2] have shown that it is NP-hard generally. To measure the reliability of networks more accurately, A.H.Esfahanian and S.L.Hakimi[3] proposed the concept of restricted-edge-connectivity. Q.L.Li and Q.Li[4] proposed the concept of super-restricted-edge-connectivity when they researched the reliability of the circular graphs in 1998.In this thesis, we mainly continue to discuss the properties ofκ-restricted-edge-connectivity on the basis of previous work.In the first chapter, we give a brief introduction about the basic concepts, ter-minologies and symbols which will be used in this thesis. In the meantime, we also give some related research backgrounds and some known results.Graphs in this paper are finite, simple, undirected and connected. Let G=(V, E) be a graph with vertex set V and edge set E, and denote n(G) =｜V｜. For X C V(G), let G[X] be the subgraph induced by X, X= V(G)-X. For A,B(?)V(G), let [A, B] be the set of edges with one vertex in A, and the other vertex in B. Denote a(X) =｜[X,V-X]｜.Let k be a positive integer, G= (V,E) be a connected graph of order n(≥2k). An edge set S (?) E is called a.κ-restricted-edge-cut and denoted by.Rκ-edge-cut for short if G - s is disconnected and every component of G-S has'at least k. vertices.The size of a minimum Rκ-edge-cut of graph G is called theλk-restricted-edge-connectivity of G, denoted byλk(G) or simplyλk.λ2 is writed as A'also. G is calledλk-connected ifλk(G) exists.Define§k(G)=min{a(X):x(?)V(G),｜X｜= k,G[X] is connected}.Aλk-connected graph G is calledλk-optimal ifλk(G)=§k(G).Moreover, G is super-λk-connected, in short, super-λk, if every minimum k-restricted-edge-cut of G iso-lates one connected subgraph of order k. In Chapter 2,firstly,Fan-type conditions forλ3-optimaIity and superiority in general graphs are studied.The second,Fan-type Conditions forλ3-optimality andλ3-superiority in bipartite graphs are presented.At last,Fan-type conditions forλ'-optimality andλ'-superiority in triangle-free graphs are studied.We obtain the following results:Theorem 2.1.2 Let G be a connected graph of order n≥6 satisfying the three conditions as follows:(a)max{d(x),d(y)}≥[n/2]-2 for each pair x,y∈V(G)with d(x,y)=3,(b)max{d(x),d(y)}≥[n/2] for each pair x,y∈V(G)with d(x,y)=2,(c)there exists a verticeυin every subgraph K4 satisfying d(υ)≥[n/2]+2, then G isλ3-optimal except G is a spide of three feet.If changing d(·)to d(.)一1 the conditions still bold,then G is super-λ3.Theorem 2.2,2 Let G be a connected bipartite graph of order n≥6 satisfying the two conditions as follows:(a)max{d(x),d(y)}≥[(n+2)/4] for each pair x,y∈V(G)with d(x,y)=3,(b)max{d(x),d(y))≥[(n+2)／4]+2 for each pair x,y∈V(G)with d(x,y)=2, then G is A3-optimal.If changing d(.)to d(.)一1 the conditions still hold,then G is super-λ3.Theorem 2.3.2 Let G be a connected triangle-free graph of order n≥4.If for all pairs.u,υ∈V(G)with d(u,υ)=2,we have max{d(u),d(υ))≥[(n+2)／4]+1,then G isλ'-optimal.If changing d(.)to d(.)一1 the conditions still hold,then G is super-λ'.In Chapter 3,we will show some neighborhood intersection conditions for graphs to beλ3-optimal and super-λ3.We have the following results:Definition 3.1.4 Class G'consist of graphs G with:for someλ4-cut S=(X,X],｜S｜(x)｜≥2 for every vertex x,and exists a vertex p∈N(u)∩N(υ)N(训)∩X2(orX2) for any 3-cycle H=G[{u,υ,w)]in G[X2](or G[x2]).Where s(x)is the edge set incident with x in S,X2={x∈X:｜S(x)｜=2},X2={x∈X:｜S(x)｜=2}.Theorem 3.1.5 Let G(?)G*be a graph with order n≥6,and satisfying·｜N(u)∩N(υ)｜≥3 for all pairsu,υof nonad jacent and lieing in no K4一e's,otherwlse,｜N(u)∩N(υ)｜≥4,then G isλ3-optimal.Theorem 3.1.13 Let G be a triangle-free connected graph with order n≥6.If max{d(u),d(υ)}≥[n+2-4]+1 for all pairs u,υWith d(u,υ)=2 or 3,and｜N(u)nN(υ)｜=1 for d(u,υ)=2,then G is A3-optimal.Definition 3.2.1 Letting. V(κθ)={x1,x2,…,x8),V(K4)={y1,y2,y3,y4},G8,4 consist of graphs(Kθ∪κ4)+(x2i-1yi,x2iyi｜i=1,2,3,4}with some x2i-1x2i,1≤i≤4 deleted.Theorem 3.2.12 Let G be a graph with order n≥6.If｜N(u)nN(υ)｜≥4 for all pairs u,υof nonadjacent vertices andξ3(G)≤[n/2]+3,and G(?)G8,4,then G is super-λ3.Theorem 3.2.14 Let G be a graph with order n≥6. If｜N(u)∩N(υ)｜≥5 for all pairs u,υof nonadjacent vertices and｜N(u)∩N(υ)｜≥4 for all pairs u,υof adja-cent vertices,then G is super-λ3 or G∈L2(n／2,3),in which L2(n／2,3)is the class of (2+n／2)-regular graphs obtained froin 2Kn／2 by adding edges.Theorem 3.2.16 Let G be a graph with order n≥6.If｜E(G[N(u)∩N(υ)])｜≥9 for all pairs u,υof nonadjacent vertices,then G is super-λ3 or G∈L2(n／2,3)(n≥8).In Chapter 4,we mainly give some degree sequence conditions for the optimality and super-connectness ofκ-restricted-edge-connectivity in graphs.Theorem 4.4 Let p≥2,κ≥5 be integers,G be aλk-connected graph of order n>κ(κ-1)with clique numberω(G)≤p and degree sequence d1≥d2≥…≥dn=б. If then G is Ak—optimal.Theorem 4.5 Letρ≥2,κ≥5 be integers,G be aλκ-connected graph of order n>κ(κ1)with clique numberωρ(G)≤p and degree sequence dl≥d2≥···≥dn=&. If then G is super-λκ.