The Existence And Upper Bound Of K-Restricted Edge Connectivity Of Graphs

With the development of social economy, science and technology, the relationship between man and networks becomes more and more closely. Naturally, the research about the reliability and fault-tolerability of networks is the inevitable trend of social development, and it is one of the most active researches at home and abroad these years. As we know, edge-connectivity plays an important role in the connectivity of graphs. But unfortunately, the classical concept of the edge-connectivity has three obvious deficiencies. First, even two graphs with the same edge-connectivity may have different reliability. Second, sometimes we can not identify the different types of disconnected graphs which result from removingκ-vertex-cuts orλ-edge-cuts. In other words, we haven't considered the damage of the vertex-cuts and the edge-cuts. Third, the shortcoming of using them as measures of fault tolerance is that it is tacitly assumed that all elements in any subset of G can potentially fail at the same time. Consequently, to compensate for these shortcomings, it seems natural to generalize the notion of classical edge-connectivity. Since Harary proposed the concept of conditional edge-connectivity in 1983, after about twenty years development, the contents in conditional edge-connectivity become more rich and specific, including super edge-connectivity, extra edge-connectivity, restricted edge-connectivity, and so on.The design and analysis of large-scale reliable networks typically involve sometypes of graph modles. There are a variety of theoretical problems corresponding to different modles. One important modle is a network as follows: a graph G = (V, E) together with a probability of failure p∈(0, 1) associated with each edge. We assume that the edges fail independently with the same probability, 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).Clearly, the smaller P(G, p) is, the better the reliability of G is. Therefore, the problem of determining P(G, p) for a given graph G and p has received considerable attention in research of networks' reliability. However, Proven and Ball have shown that the calculation ofP(G, p) for an abitrary graph G is N P-hard. To solve this problem, Esfahanian and Hakimi proposed the concept of restricted edge-connectivity. In this paper, we mainly continue to discuss the related properties of restricted edge-connectivity on the basis of previous work.In this paper, we use k denoting a positive integer,ω{G) denoting the size of a maxinum clique of graph G. 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.Definition 1.3 Let G be a connected graph of order n(≥2k). An edgeset S (?) E is a k-restricted edge cut denoted by R_k-edge cut for short if G - S is disconnected and each component of G - S has at least k vertices. The size of a minimum R_k-edge cut of graph G is its k-restricted edge connectivity, denoted byλ_k(G),or simplyλ_k.If graph G contains R_k-edge cuts, then G is calledλ_k-connected.Definition 1.4 Let X, Y be two disjoint subsets of V or two vertex-disjoint subgraphs of G = (V, E). The set of edges with one end in X and the other in Y is denoted by [X, Y].We Simplify [X, Y] as [x,Y] if X = {x}.Denote I(X) = [X, V - X],(?)(X)= | I(X) | is called external degree of X.Letξ_k(G)=min {(?)(X) :|X|= k, and G[X] is connected },where G[X] denotes the subgraph of G induced by X. Let (?) = V(G) - X. If [X, (?)] is a λ_k-cut of G, then X is called aλ_k-fragment. Clearly, if X is aλ_k-fragment, so is (?). Aλ_k-fragment with minimum cardinality of G is called aλ_k-atom. The cardinality of aλ_k-atom is denoted byÏ„_k(G).Definition 1.14 Aλ_k-connected graph G is calledλ_k-optimal,ifλ_k(G) =ξ_k(G).In the second chapter, we mainly study the upper bound of the 5-restricted edge connectivity and have the following results:Theorem 2.3 Let G be a connected graph with order at least 18.If G contains 5-restricted edge cuts, thenλ₅(G)≤ξ₅(G) if and only if G doesn't belong to (?)₅.Where (?)₅ is defined as follows: Connected graphs with order at least 18, containing exactly a complete graph K₅,and each vertex of K₅ is joint to a connected graph with order at most 3 by exactly one edge.Theorem 2.5 Let G be aλ₅-connected triangle-free graph with order at least 18. If G is notλ_k-optimal, thenÏ„_k(G)≥max{6,2δ(G) - 4}.Theorem 2.6 Let G be aλ₅-connected graph,δ(G)≥6,U is aλ₅-atom of G. If G is notλ_k-optimal, then for each v∈U,we have d_G|U|(v)≥4.In the third chapter, we mainly study the existence of the k-restricted edge connectivity of regular graphs and obtain the results as follows:Theorem 3.1.5 If G is a (k - 3)-regular connected graph (k≥5) of order at least 2k, then G contains k-restricted edge cuts if and only if G does not belong to G_k-3^<sup>∪G_k-3^k-2 and G is not isomorphic to G₁₇⁴ when k = 7.Here, we denote the set of this kind of graph G as G_k-3^<sup> :G is a (k - 3)-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 each remaining component is k - 1 or k - 2. Denote the set of this kind of graph G as G_k-3^k-2:G is a (k - 3)-regular connected graph of order 3k - 3 or 3k - 4 with k≥5,and G contains a triangle T, if any, and each vertex of T is joint to a connected graph of order k - 2 or k - 3 by some edges. Denote the set of this kind of graph G as G₁₇⁴ : G is a 4-regular connected graph of order 17, and G contains an edge e and three connected graphs G₁,G₂,G₃ and each with order 5( where G_i is a graph obtained by deleting two edges incident with the same vertex from a complete graph K₅,i=1,2,3 ). And each vertex of e is joint to the vertex which degree is 2 of G₁,G₂ and G₃.Theorem 3.2.3 If G is a (k - 4)-regular connected graph (k≥6) of order at least 2k, then G contains k-restricted edge cuts if and only if G does not belong to G_k-4^?∪G_k-4^k-2 and G is not isomorphic to G₁₇⁴ when k = 8.Here, we denote the set of this kind of graph G as G_k-4^?:G is a (k - 4)-regular connected graph of order at least 2k with k≥6,and G contains a cutvertex, if any, whose deletion disconnects G and the order of each remaining component is k - 1,k - 2 or k - 3. We denote the set of this kind of graph G as G_k-4^k-2:G is a (k - 4)-regular connected graph of order 3k - 3,3k - 4,3k - 5 or 3k - 6 with k≥6, and G contains a triangle T, if any, and each vertex of T is joint to a connected graph of order k - 2, k - 3 or k - 4 by some edges.In the fourth chapter, we mainly give some sufficient conditions for a graph to beλ_k-optimal.We have the following results:Theorem 4.5 Let G be a graph of order n(≥2k), and d(u)+d(v)≥n+2k-4 for every pair of nonadjacent vertices u and v in V. If G is not isomorphic to G_k^, then G isλ_k-optimal.Where G_kⁱs defined as follows: a connected graph of order n(≥2k) and its vertex set can be divided into two parts V₁ and V₂,with |V₁|,|V₂|≥k.If there exists x_i∈V_i,such that d(x_i) = |V_i| + k - 2,and x_i is a k - 1- saturated vertex of [V₁,V₂] ( that is to say:x_i is incident with k - 1 edges of [V₁,V₂]), i - 1,2, then x₁ and x₂ are not adjacent.Theorem 4.9 Let G be aλ₃-connected triangle-free graph of order n with degree sequence d₁≥d₂≥…≥d_n =δ. Ifthen G isλ3-optimal.Theorem 4.10 Let p≥3 be an integer, and let G be aλ₃-connected graph of order n with clique numberω(G)≤p and degree sequence d₁≥d₂≥…≥d_n = δ(G).Ifthen G isλ₃-optimal.