Existence And Bound On K-restricted Edge Connectivity Of Graphs

study of graph theory started over two hundreds years ago. The earliest knownpaper is due to Euler (1736) about the seven bridges of K¨onigsberg. Since 1930s,graph theory has developed very fast and numerous results on graph theory sprungforth. There are many nice and celebrated problems in graph theory, such as Hamil-tonian problem, four-color problem, Chinese postman problem, etc. Moreover, graphtheory is widely applied in chemistry, computer science, social science, biology andother disciplines. As a subfield in discrete mathematics, graph theory has attractedmuch attention from all perspectives.Restricted edge connectivity is a tool which study graphs. In fact, many prac-tical problems can be attributed to the problem of restricted edge connectivity.Therefore, the research about them is very active. In Present,networks have closelyrelationship with various aspects of people,such as work,entertainment and life.Theresearch about the reliability and tolerability of networks is very active.We know thatconnectivity plays an important role in the connectivity of graph.But the classicalconcept of the connectivity has three obvious deficiencies.First,even two graphs withthe same connectivity may be considered to have different reliability.Secondly,theydo not di?erentiate between the di?erent types of disconnected graphs which resultfrom removingκdisconnecting vertices orλdisconnecting edges.Thirdly,the short-coming of using them as measures of fault tolerance is that it is tacitly assumedthat all elements in any subset of G can potentially fail at the time.Consequently,tocompensate for these shortcomings,it would seem natural to generalize the notionof classical connectivity .Since Harary[3] proposed the concept of conditional con-nectivity in 1983,after several decades of development, the contents in conditionalconnectivity become more rich and specific.The design and analysis of reliable large-scale networks typically involve some type of graph theoretic modle.There are a variety of theoretical problems that arisedepending on the exact network reliability model that is used.One important modelis a network of such as:a graph G together with a probability of failure p associ-ated with each edge.We assumed that the edge failure probabilities are equal andindependent,it is also assumed that the nodes do not fail.Then the probability thatG is disconnected can be expressed as .Where e is thetotal number of edges in G,Ch is the number of edge cuts of size h.Therefore,thereliability of G is 1 -P(G,p).The problems of determent P(G,p) for given G andp have received considerable attention in the reliability literature.However,Provenand Ball [4] have shown that the calculation of P(G,p) for an arbitrary graph Gbelongs to the class of computationally intractable problems known as NP-hard.Tosolve this problem,Esfahanian and Hakimi [5]proposed the concept of restrictedconnectivity. In this paper, we mainly continue to discuss the related properties ofrestricted 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, wealso give some related research backgrounds and some known results. In the secondchapter, we mainly study the k-restricted edge connectivity of graphs (D(G)=2) andobtain the result as follows:Theorem 2.2 Let G be a graph (D(G)=2),then arbitraryexist. Or the graph Just contain a Saturation vertex and it is the cut vertex.In section I of the third chapter, we mainly study the existence and bound onrestricted edge connectivity of 3-regular graphs and give the following results:Theorem3.1.3 Let G be a 3-regular connected graph of order at least 12 ,ifG is not a 6-?ower, thenλ₆(G) exist.In section II, we mainly study the existence and bound on restricted edgeconnectivity of k-regular graphs and obtain the result as follows:Theorem 3.2.6 Let G be a k-regular connected graph of order at least 14with k≥2. If G contains 7-restricted edge cut, thenλ₇(G)≤ξ₇(G).