The Research Of K-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.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ρ. 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. 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[4].For further study, Esfahanian and Hakimi proposed the concept of restricted edge connectivity in [5]. For more accurate results, Fabrega and Fiol improved the concepts to k-restricted edge cut and k-restricted edge connectivity in [6]. In this paper, we mainly continue to discuss the related properties of restricted connectivity on the basis of previous work.The first chapter of this paper gives a brief introduction about the basic concepts, 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. 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 k vertices, then we speak of an k-restricted edge cut. The minimum cardinality over all k-restricted edge cuts in G is called k-restricted edge connectivity, denoted byλ_k(G). A connected graph G isλ_k-conected, ifλ_k(G) exists. An k-restricted edge cut S in G is called aλ_k-cut, if |S|＝λ_k.For two disjoint vertex sets X,Y(?)V(G), denote by [X, Y] the set of edges with one end inX and the other in Y. Define I(X)＝|[X,(?)]|,ξ_k(G)＝min{I(X):|X|＝k, G[X]is connected}.A connected graph G withλ_k(G)＝ξ_k(G) is said to beλ_k-optimal.Furthermore, if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k, then G is said to be super－λ_k.In second chapter, we study the optimality of k-restricted edge connectivity in ordinary biparitte. We will give the following results:Theorem 2.2 Let G be connected bipartite andδ(G)≥3. If d{x)＋d(y)≥2(?)＋4, for each pair x, y in V(G) sunch that d(x, y)＝2 then G isλ₃-optimal.Theorem 2.4 Let G be connected bipartite with n(G)≥11andδ(G)≥3. If d(x)＋d(y)≥2(?)＋6, for each pair x, y in V(G) sunch that d(x, y)＝2 then G isλ₄-optimal.Theorem 2.5 Let G beλ₅-connected bipartite withδ(G)≥5. If d(x)+d(y)≥ (?),for each pair x,y in V(G) sunch that d(x, y)＝2 then G isλ₅-optimal.In the third chapter, we study the existence of k-restricted edge connectivity in complete p-partite graph and the optimal of k-retricted edge connectivity in complete biparitte. We will give the following results:Theorem 3.4 Let G be complete p-partite graph K_{(r1),(r2),…,(rp)}, G≠K_1,(n－1) andt₁＋r₂＋...＋r_p≥2k, thenλ_k exist andλ_k(G)≤ξ_k(G).When p equals 2 we conclude :Collorary 3.5 Let G be the complete biparitte K_r,s and |G|≥2k, r,s≥2, thenλ_k exist andλ_k(G)≤ξ_k(G).Theorem 3.6 Let G be the complete biparitte K_r,s.and then G isλ_k-optimal if only if |G|≥2k, r,s≥2.In the fourth chapter, this paper will give a sufficient condition for graph to beλ₃－optimal:Theorem 4.2 Let |G|≥6 ,δ≥3 and D≤g－4 thenλ₃(G)=ξ₃(G).