The 4-restricted Edge Connectivity Of Graphs

The restricted edge connectivity problem of graphs and some other graph theories are all from the study of the big network design and reliability analysis.In our living ,the restricted edge connectivity problem has a big application, and with the development of the field some scholars presented and studied a few restricted edge connectivity problems with different restrictions.If not explicity,all graphs considerd in this paper are simple and connected with order at least eight. when studying network reliability,one often considers such a kind of model whose nodes never fail but links(edges) fail independently of each other with suffiently small equal probabilityρ.which is often called Moore-shannon network model[1, 2]. Let M be a Moore-shannon network model,denoted by C_h the number of its edge cuts of size h. If M contains exactly e links,then its reliability,the probability it remains unconnected,can be expressed asclearly,the smaller P(G,ρ) is,the more reliable the network is.If one can determine all the cofficients C_h, he detemines the reliability.But unfortunately,Provan and Ball shows in [3] that it is NP - hard to determine all these cofficients.Denote byΩ(n, e) the set of graphs with n vertices and e edges.To minimize P(G,ρ) inΩ(n, e) whenρis sufficiently small,the edge connectivity plays an important role.For G₁,G₂∈Ω(n,e),ifλ(G₁) >λ(G₂), the P(G₁,ρ) < P(G₂,ρ) whenρis sufficiently small[6].For further study,Esfahanian and Hakimi proposed the concept of restricted edge connectivity in [4].For more accurate results,Fabrega and Fiol improved the concepts to k-restricted edge cut and k-restricted edge connectivity in [5].And the study of k = 1,2,3 have gotten many achievements.The first chapter of this paper gives a brief introduction about the basic conceps,terminologies and symboles which are used in this paper.let G be a graph with vertex set V(G) and edge set E(G). For X (?) V(G),let G[X] be the subgraph induced by X, (?) = V(G) - X,and [X, (?)] be the set of edges in G with one end in (?) and the other in (?). If G is a connected graph and S (?) E(G).such that G - S is disconnected,and each compont of G - S consists of at least four vertices,then we speak of an 4- restricted edge cut.The minimum cardinality over all 4-restricted edge cuts in G is called 4-restricted edge connectivity,denoted byλ₄(G). A connected graph G isλ₄-conected,ifλ₄(G) exists.An 4-restricted edge cut S in G is called aλ₄-cut,if |S| =λ₄.In second chapter,we study the existence of 4-retricted edge connectivity. A graph F of order n≥8 is called a 4-fiower,if it contains a cut-vertex s such that every component of F - s has order at most 3. A graph is called a triangle spanning graph,if it stick a subgraph of triangle on each vertex of a triangle. With these special graphs we characterize the graph class which is notλ₄-connected and order at least 9.In [20] J.P.Ou give a result that forλ₄- connected graphs G of order n≥11 thatλ₄(G)≤ξ₄(G),whereξ₄(G) is defined byξ₄(G)=min{|[X,(?)]|:X(?)V(G),|X|=4,G[X] is connected} ,In third chapter we present a brief proof.Aλ₄-graph G is calledλ₄-optimal,ifλ₄(G) =ξ₄(G).If [X,(?)] is aλ₄-cut, then X(?)V(G) is called aλ₄-fragment.Let r₄(G) = min{|X|:X is aλ₄- fragment of G}. In forth chapter we prove that aδ(G)≥4 andλ₄-connected graph G is notλ₄-optimal,then r₄(G)≥(?) +1.Finally,we study theλ₄-optimality of complete bipartite graph.In this paper we have the following theorems:Theorem 2.6 A connected graph of n≥9 is notλ₄-connected if and only if G is either a 4-flower or a triangle spanning graph. Theorem 4.1.3 Let G be aλ₄-connected graph,δ(G)≥4,if G is notλ₄-optimal,then r₄(G)≥(?)+ 1.Theorem 4.2.3 Let G be aλ₄-connected and triangle -free graph.If G is notλ₄- optimal, then r₄≥max{5,2δ(G)-3}.Theorem 4.3.1 Let r,s≥2 be integers,r + s≥8.Thenλ₄(K_r,s) exists andλ₄(K_r,s)≤ξ₄(K_r,s).Theorem 4.3.2 Let r,s≥2,r + s≥8 be integers.Then K_r,s isλ₄-optimal.