|
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. 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 sufficiently small equal probabilityρ. Let G be a network model, denoted by Ch the number of its edge cuts of size h. If G 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 Ch, he detemines the reliability. But unfortunately, Provan and Ball shows in [1] 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 G1,G2∈Ω（n,e）, ifλ（G1） >λ（G2）, the P（G1,ρ） < P（G2,ρ） whenρis sufficiently small. For further study, Esfahanian and Hakimi proposed the concept of restricted edge connectivity in [14]. For more accurate results, Fabrega and Fiol improved the concepts to k-restricted edge cut and k-restricted edge connectivity in [16]. And the study of it have gotten many achievements. The first chapter of this paper, we give a brief introduction about the basic conceps, terminologies and symboles which will be used in this paper. In the meantime we also give some related research backgrounds and some known results. Let G = （V, E） be a graph with vertex set V（G） and edge set E（G） and note n（G） = |V|. 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 X and the other in （?）. If G is a connected graph with order at least 2k and S （?） E（G）, such that G - S is disconnected, and each component of G - S consists of at least k vertices, then we call it a k- restricted edge cut or Rk- edge cut for short. The minimum cardinality over all Rk- edge cut in G is called k-restricted edge connectivity, denoted byλk（G）. Clearly,λ（G） =λ1（G）≤λ2（G）≤…≤λk（G）. A connected graph G isλk-conected,ifλk（G） exists. Let X∈V（G）,α（G） = |[X,（?）]|. Noteξk（G） = min(α（X） : |X| = k and G[X] is connected}. we can easily to say thatξ1（G） =δ（G） withδ（G） is the minimum degree of G. We call a graph G isλk-optimal, ifλk（G） exists andλk（G） =ξk（G）. Also we call a graph G is super-λk, if every Rk- edge cut isolated a connected subgraph of order k.Harary gave the definition of generalized restricted edge connectivity at the first time. Generally, for two integer p, q≥1, a connected graph G isλp,q-connected if it contains an edge cut whose removal results in two components containing at least p and at least q vertices. Rautenbach and Volkmann gived us some properties aboutλ2,q-connected in [2].In the second chapter, we are mainly to think about the properties ofλ3,q-connected, which make the main rusult in [26] to become the corollary of the main results of this chapter.In the thrid chapter, we are mainly to study Afc-optimal and super-λk with k = 3,4 of the graph. We will give: a minmurn degree for graphs to beλ3-optimal and super-λ2 connected; a minmum degree for graphs to beλ4-0optimal and super-λ3 connected and a sum degree condition for graphs to beλ4-optimal and super-λ4 connected.In the fourth chapter we will give a degree sequence for graphs to beλk-optimal.In this paper we have the following theorems:Theorem 2.3 Let n, q be two integers such that n≥max{7, q + 3} and q≥3,（i）a connected graph G of order n≥2q - 1 is notλ3,q-connected if and only if G∈Wn*.（ii）a connected graph G of order n = 2q - 2 is notλ3,q-connected if and only if（iii）a connected graph G of order n = 2q - 3 is notλ3,q-connected if and only ifG∈{Wn*,S*（q-1,0,q-2）,S*（q-2,1,q-2）,R*（q-2,1,q-2）}.and the new-constructed graphs define as Definition 2.1 , 2.2.Corollary 2.6 For an integer t≥1 and 0≤r≤5, let q = 6t + r. If G is a connected graph of order n≥q + 3 that contains a cycle C of length l with l≥3t + 5, then G isλ3,q-connected.Theorem 3.1.5 Let G be a connected graph of order n≥10 and letδ（G）≥[n/2] - 2, If for each 4-cycle C there exists at least one vertex w such that d（w）≥[n/2] + 2, then G isλ3-optimal. Furthermore, if for each triangle T there exists at least one vertex v such that d（v）≥[n/2], then G is super-λ2 connected.Theorem 3.2.4 Let G be aλ4connected graph of order n≥11 and letδ（G）≥[n/2] - 3. If for each induced 5-cycle and each sticking graph of two triangle there exist at least one vertex u except the sticking vertexs such that d（u）≥[n/2] - 1, for each induced 5-cycle there exists at least one vertex v such that d（v）≥[n/2] + 1 and for each triangle K4 - e there exists at least one vertex w such that d（w）≥[n/2], then G isλ4-optimal. Furthermore, if n≥12, then G is super-λ3 connected.Theorem 3.3.2 If G be aλ4-connected graph of order n≥11 satisfying the following three conditions, then G isλ4-optimal.（i）For two vertices x and y with d（x, y） =t such that d（x）+d（y）≥2[n/2] - 2t+1（t = 2,3,4）,（ii）for each induced 4-cycle there exists at least one vertex u such that d（u）≥[n/2] +1,（iii）for each triangle K4 - e there exists at least one vertex v such that d（v）≥[n/2]+3.Theorem 3.3.5 If G be aλ4-connected graph of order n≥11 satisfying the following three conditions then G is super-λ4 connected.（i）For two vertices x and y with d（x, y） = t such that d（x）+d（y）≥2[n/2] -2t+3（t= 2,3,4）, （ii）for each induced 4-cycle there exists at least one vertex u such that d（u）≥[n/2]+2,（iii）for each K4 - e there exists at least one vertex v such that d（v）≥[n/2] + 4.Theorem 4.3 Let G = （V, E） is aλk-connected graph of order n with girth g > k + 1, if for every subgraph H of G such that |E（H）|≤|V（H）|2/g,λk（G）≤ξk（G） and G has degree sequence d1≥d2≥…≥dn =δsatisfying:then G isλk-optimal.
|