Sufficient Conditions For K-Restricted Edge Connectivity To Be λ_k-Optimal And Super-λ_k In Graphs

Nowadays, in the information age that social economy, science and technology de-velop rapidly, networks becomes more and more important in every aspects of people's life. The various researches about networks have attracted increasing attention, and the research about the reliability and fault-tolerability of networks has.been one of the fo-cal points of worldwide attention. As is known to all, edge connectivity is a parameter which plays an important role in the connectivity of graph. But the concept of classical edge connectivity has some obvious deficiencies. Firstly, even two graphs with the same edge connectivity may be considered to have different reliability. Secondly, sometimes we can not identify the different types of disconnected graph which result from removingκdisconnecting vertices or A disconnecting edges. In other words, we haven't considered the damage from removing vertex-cuts or the edge-cuts. Thirdly, it is tacitly assumed that all elements in any subset of graph can potentially fail at the same time. Conse-quently, to compensate for these shortcomings, it seems natural to generalize the notion of classical edge connectivity. Since F.Harary proposed the concept of conditional edge connectivity in 1983, after about twenty years development, the contents in conditional edge connectivity become richer and more specific, including super edge connectivity, extra edge connectivity, restricted edge connectivity and so on.The reliability and fault-tolerability of large-scale networks typically involve some types of graph theoretic model, and the underlying topology of an interconnected network is usually modeled by a graph in which the vertices and edges represent the nodes and links of networks. There are a variety of theoretical problems corresponding to different models. One important model is a graph G=(V, E) as follows:We assume that the vertices do not fail meanwhile the edges fail independently with the same probabilityρ∈(0,1). If the number of edges of G is denote byεand the number of edge cuts of size i is denoted by Ci, then the probability that G is disconnected can be expressed as whereλ(G) is the edge connectivity of G. It follows easily that the reliability of G is 1-P(G,ρ). Clearly, the more smaller P(G,ρ) is, the more reliable the network is. In order to determine the reliability of networks, we should determine all the coefficients Ci. However, J.S.Provan and M.O.Ball have shown that it is N P-hard to determine Ci of a graph.To measure the reliability of networks more accurate, A.H.Esfahanian and S.L.Hakimi proposed the concept of restricted edge- connectivity of graphs. J.Fabrega and M.A.Fiol improved the concept to k-restricted edge cut and k-restricted edge connectivity. Fur-thermore, Q.L.Li and Q.Li proposed the concept of super restricted edge-connectivity. So far, there have.been many extensive researches in this field. In this thesis, we mainly continue to discuss the properties of restricted edge connectivity on the basis of previous work.This thesis consists of four chapters. In the first chapter, we give some related research backgrounds and some known results, in the meantime, we give a brief introduc-tion about the basic concepts, terminologies and symbols which will be used in this paper.The graphs in this paper are finite, simple, undirected and connected. Let G= (V, E) be a connected graph with vertex set V(G) and edge set E(G), and let n(G)=│G│denote the order of G. For (?)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. The out-degree of X is denoted by (?)(X)=│[X,X]│.Let k be a positive integer and G be a connected graph of order n(≥2k). An edge set S(?)E is called a k-restricted edge cut if G-S is disconnected and each component of G-S has at least k vertices. The k-restricted edge connectivity of G is defined asλk=λk(G)=min{│S│:S is a k-restricted edge cut of G},the minimum k-restricted edge cut S is called aλk-cut.If graph G containsλk-cuts,then G is called aλk-connected graph.k-Restricted edge connectivity is an important parameter in measuring the re-liability and fault- tolerability of networks.Letξk(G)=min{(?)(F):F is a connected subgraph of G,│F│=k};particularly,ξ(G)=min{dG(u)+dG(v)-2:uv∈E(G)}is the minimum edge degree of G.It has been shown thatλk(G)≤ξk(G)holds for many graphs.Ifλk(G)=ξk(G),then G isλk-optimal.Moreover G is super-λk connected, in short,super-λk if every minimum k-restricted edge cut of G isolates one connected subgraph F of order k.In the second chapter,we mainly studyλ4-optimality of graph.We give some suffi-cient conditions for a graph to beλ4-optimal in terms of neighborhood intersection and local condition.We have the following results:Theorem 2.2 Let G be aλ4-connected graph with order n(≥11).If│N(u)∩N(v)│≥5 for all pairs u,v of nonadjacent vertices such that neither u nor v lies on a triangle, and│N(u)∩N(v)│≥7 for all pairs u,v of nonadjacent vertices such that either u or v lies on a triangle,then G isλ4-optimal.Theorem 2.3 Let G be aλ4-connected graph with order n(≥11).If│N(u)∩N(v)│≥5 for all pairs u,v of nonadjacent vertices,and│N(x)∩N(y)│≤2 for all edge xy in G, then G isλ4-optimal.Theorem 2.6 Let G be aλ4-connected graph with order n(≥11),satisfying│N(u)∩N(v)│≥1 for all pairs u,v of nonadjacent vertices andξ4(G)≤[n/2]. Let each induced subgraph of G satisfies:the degree 1 verte w of the identification of P2 and K1,3+,P2 and C4 satisfies d(w)≥[n/2]-4;the degree 1 vertex w of K1,3+ satisfies d(w)≥[n/2]-2;for each C5 there exists one vertex w such that d(w)[n/2]-2;for each C4 there exists one vertex w such that d(w)≥[n/2];for each K4,K4- there exists one vertex w such that d(w)≥[n/2]+2,then G isλ4-optimal.In the third chapter,we mainly study triangle-free graph to beλk-optimal and super-λk.We give some sufficient conditions for a graph to beλk-optimal and super-λk in terms of neighborhood intersection,meanwhile we give the relationship betweenλ4-optimal graph and super-λk graph.We have the following results:Theorem 3.1.2 Let G be aλ4-connected triangle-free graph with order n(G)≥11. If│N(u)∩N(v)│≥3 for all pairs u,v of nonadjacent vertices,then G isλ4-optimal.Theorem 3.1.3 Let G be aλ4-connected triangle-free graph with order n(≥11). If│N(u)∪N(v)│≥4 for all pairs u,v of nonadjacent vertices,then G is super-λ4. Lemma 3.2.3 Let k be a positive integer,G be a connected triangle-free graph with order n(≥2k).If│N(u)∩N(v)│≥k+1 for all pairs u,v of nonadjacent vertices,but G is not super-λk,then either G(?)Kk+1,n-k-1 or the set U*={v∈U:│[v,U]│≤k/2}≠Φfor anyλk-fragment U with│U│≥K+1,│U│≥k+1.Theorem 3.2.2 Let k be a positive integer,G be a connected triangle-free graph with order n(≥2k).If│N(u)∩N(v)│≥k+1 for all pairs u,v of nonadjacent vertices, then G is super-λkTheorem 3.3.1 Let G be aλ4-optimal graph.(a)Ifδ(G)≥6,then G isλi-optimal for i=1,2,3 and super-λi for i=1,2;Ifδ(G)>6,then G is also super-λ3.(b)Let G be a triangle-free graph.Ifδ(G)≥4,then G isλi-optimal for i=1,2,3; Ifδ(G)>4,then G is super-λi for i=1,2,3.In the fourth chapter,we mainly study sufficient conditions for a bipartite graph to beλk-optimal. We give a sufficient condition for a bipartite graph to beλk-optimal in terms of neighborhood intersection and the Nordhaus-Gaddum conclusion.We have the following results:Theorem 4.1.2 Let G=Kr,s(3≤r≤s).Then G satisfies the property as follow: (a)λ3(G)+λ3(G)=2r+s-4, (b)ξ3(G)+ξ3(G)=5r+s-13, (c)λ3(G)+λ3(G)≥min{ξ3(G),ξ3(G)}+5. Theorem 4.1.3 Let G=Kr,s(4≤r≤s).Then G satisfies the property as follow:Theorem 4.2.1 Let G(X∪Y,E)be a bipartite graph with order n(≥2k)and Fk be an arbitrary connected subgraph of order k in G.If│N(u)∩N(v)│≥k for each pairs u,v∈X and u,v∈Y,and for someλk-cut[U