Some Results On K-restricted Edge Connectivity Of Graphs

In present, net works have closely relationship with various aspects of people,such as work,entertainment and life.The reserch about the reliability and tolerability of networks is very active.We know that edge connectivity plays an importent role in the connectivity of graph.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 removingκdisconnecting vertices or A disconnecting edges.Thirdly.the shortcoming of using them as measures of fault tolerrance is that 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 would seem natural to generlize the notion of classical edge connectivity .Since Harary proposed the concept of conditional connectivity in 1983.after about twenty years development, the contents in conditional connectivity become more rich and specific.including super connectivity.extra edge connectivity, restricted edge connectivity, and so on.The design and analysis of reliable large-scale networks typically involve some types of graph theoretic modle.There are a variety of theoretical problems that arise depending on the exact network reliability modle that is used.One importent modle is a network of such as:a graph G together with a probability of failure p associated with each edge.We assumed that the edge failure probabilities are equal and independent.it is also assumed that the nodes do not fail.Then the probability that G is disconnected can be expressed asWhere e is the total number of edges in G.C_h is the number of edge cuts of size h.Therefore,the reliability of G is 1-P(G. p) .The problems of determing P(G.p) for given G and p have received considerable attention in the reliability literature.However. Proven and Ball have shown that the calculation of P(G, p) for an abitrary graph G belongs to the class of computationally intractable problems known as NP-hard.To solve this problem,Esfahanian and Hakimi proposed the concept of restricted connectivity. In this paper, we mainly continue to discuss the related properties of restricted connectivity on the basis of previous work.In the first chapter, we give a brief introduction about the basic concepts. terminologies and symbols which will be used in this paper. In the meantime, we also give some related research backgrounds and some known results.Definition1.2 An k-restricted edge cut.or simply an R_k-edge cut.is an edge cut S of a connected graph G such that every component of G- S has order at least k.The size of a minimum R_k-edge cutof graph G is its k-restricted edge connectivity,denote byλ_k(G),or simplyλ_k.If graph G contains R_k-edge cuts, then G isλ_k-connected.Definition1.3 For X. Y (?) V(G).let [X. Y] be the set of edges with one end in X and the other end in Y.Simply [x. Y] as [X.Y] . Denote (?)(X) = | [X, V - X] |. Letξ_k(G)=min {(?){X) :|X |= k. G[X] is connected },Where G[X] denotes the subgraph of G induced by X. Aλ₂-connected graph G is calledλ₂-optimal,ifλ₂(G) =ξ₂(G).In the second chapter, we mainly study the existence and upper bound of the k-restricted edge connectivity (k≤6)of regular graphs and 2-connected graphs and give the following results:Theorem2.1.7 Let G be a regular connected graph of order at least 10 . Then G contains 5-restricted edge cuts andλ₅(G)≤ξ₅(G).Theorem2.2.2 If G be a 2-connected graph with order at least 8 which is not in any G,then G contains 4-restricted edge cuts and λ_k(G)≤ξ₄(G)Where G is defined as follows:If F is a connected graph with order of four and edge at least five.Suppose the vertex set of F is V(F) = {a,b,c,d} and d_F (a) = d_F(c)= 3. Let G₁,G₂ are two connected graphs with order of two or there. We add four independent edges between {a, c} and G₁, G₂ to make {a. c} be adjacent to G₁, G₂ respectively.The resulting graph is denoted by G.Theorem2.3.1 Let G be a regular connected graph of order at least 12.If G contains C-restricted edge cuts.thenλ₆(G)≤ξ₆(G).In the third chapter, we mainly study the existence of the krestricted edge connectivity of (k - 2)-regular graphs and obtain the result as follows:Theorem 3.1 If G is a (k-2)-regular connected graph of order at least 2k. then G contains k-restricted edge cuts if and only if G does not belong to G_k-2^*.Here,we denote the set of this kind of graph G as G_k-2^*:G is a (k - 2)-regular connected graph of order at least 2k with k≥5.And G contains a cutvertex, if any, whose deletion disconnects G and the order of every remaining component is k - 1.In the fourth chapter, we mainly give a corresponding result of the optimal of the restricted edge connectivity:Theorem 4.2 Let G be a graph of order n.and d(x) + d(y)≥n for every pair of nonadjacent vertices x and y .If G is notλ₂-optimal.then G is isomorphic to G^*.Where G^* is defined as follows:Suppose G is a connected graph with order of n and the vertex set of G can be divided two parts A and B.sign G₁= G[A].G₂ = G[B]. |G_i|= n_i(i = 1.2).S = [A.B].If u∈V(G₁).v∈V(G₂).d_G1(u) =n₁-1.d_G2(u)= n₂- 1 and u,v are both single saturated vertices.then u and r are not adjacent in G.We denote this kind of graph G as G^*.