Optimality And Super-connectedness Of Higher-order Restricted Edge Connectivity In Graphs

In present, networks have closely relationship with various aspects of people, such as work, entertainment and life. The research about the reliability and tolerability of networks is very active. We know that edge connectivity plays an important 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λ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 seems natural to generlize the notion of classical edge connectivity. Since Harary[1] 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 important modle is a network of such as [2]:Assume that all vertices of G = (V,E) are perfectly reliable and all edges failed independently, with the same probability p, denote by N_i(G) the number of edge cuts of size. Then the probability R(G,p) of G being connectedness is gave byhereεis the number of edges of G, the edge connectivity of G, denoted byλ(G), is defined as the cardinality of a minimum edge cut. In general, it is difficult to determine N_i(G) of a graph[3]. Bauer et al.[4] defined that a graph G isλ-optimal ifλ(G) =δ(G), and G is super-λif every minimum edge cut of G isolates one vertex.The restricted edge connectivity was proposed by Esfahanian and Hakimi[8]. The restricted edge connectivity provides a more accurate measure of fault-tolerance of networksthan the classical edge connectivity. An edge set U of G is called a restricted edge cut if G - U is disconnected and every component of G - U contains no isolatedvertex. If such an edge cut exists, then the restricted edge connectivity of G, denoted byλ'(G), is defined as the cardinality of a minimum restricted edge cut, and G is calledλ'-connected. Esfahanian and Hakimi showed that each connected graph G of order n≥4 except a star K_1,n-1, isλ'-connected and satisfiesλ'(G) <ξ(G), whereξ(G)=min{d_G(u) + d_G(v)-2 : uv∈E(G)} is the minimum edge degree of G. G isλ'-optimal ifλ'(G) =ξ(G). Moreover G is super-λ' if every minimum restricted edge cut of G isolates an edge.Let k be a positive integer. For a connected graph G = (V, E), an edge set U (?) E is a k-restricted edge cut if G - U is disconnected and every component of G-U has at least k vertices. The k-restricted edge connectivity of G, denoted byλ_k(G), is defined as the cardinality of a minimum k-restricted edge cut, and G is calledλ_k-connected. k-restricted edge connectivity is an important parameter in measuring the reliability and fault toleranceof networks. Letξ_k(G)=min{(?)(F) : F is a connected subgraph of G, |F| = k}, where (?)(F) denotes the number of edges with one end in F exactly. It has been shown thatλ_k(G)≤ξ_k(G) holds for many graphs[28]. G isλ_k-optimal ifλ_k(G) =ξ_k(G). MoreoverG is super-λ_k if every minimum k-restricted edge cut of G isolates one connected subgraph F of order k.In this paper, we mainly continue to discuss the related properties of k-restricted connectivity on the basis of previous work.In the first chapter, we give a brief introduction about the basic concepts, termi- nologies and symbols which will be used in this paper. In the meantime, we also give some related research backgrounds and some known results.In the second chapter, we will show some sufficient conditions for graphs to beλ_k-optimalby using the diameter D and the girth g of G:Theorem 2.2. Let k≥3 be an integer, G be a graph with |G|≥2k,D≤g-(k + 1) and k≤δ+ 1, where D,g,δdenote the diameter, the girth and the minimum degree of G, respectively, then G isλ_k-optimal.Definite. Let G₁, G₂ be two graphs with order at least k, respectively. We define a graph family G_X containing G₁∪G₂ and satisfing | [x, G₂]| = 1 for each vertex x∈V(G₁).Theorem 2.4. Let k≥4 be an integer, G be a graph with |G|≥2k,D≤g-(k + 2) and k≤δ+ 1, where D,g,δdenote the diameter, the girth and the minimum degree of G, respectively, then G is super-λ_k except G∈G_X.In the third chapter, we will show some sufficient conditions for graphs to beλ_k-optimalby using subgraph:Theorem 3.8. Let G be aλ₃-connected graph with order n andδ≥(?) - 2, and G satisfies the following three conditions, then G isλ_k-optimal: (a)for each induced 4 cycle C₄, there exist at least a vertex x∈C₄, d(x)≥(?); (b)for each K₄-e, there exist at least a vertex y∈K₄, K₄ - e, d(y)≥(?) + 2, then G isλ₃-optimal.Theorem 3.9. Let G be aλ_k-connected graph,λ_k(G)≤ξ_k(G), F_k be an arbitrary connected subgraph with order exactly k of G and u has exactly s(1≤s≤k) neighbors in F_k . If d(u)≥(?) - k + 2s - 1, then G isλ_k-optimal.Theorem 3.11. Let G be aλ_k-connected graph,λ_k(G)≤ξ₃(G), F_k be an arbitrary connected subgraph with order exactly k of G and u has exactly s(1≤s≤k) neighbors in F_k. If d(u) > (?) - k + 2s - 1, then G is super-λ_k.In the fourth chapter, we will show some sufficient conditions for graphs to beλ_k- optimalby using neighborhood of two vertices:Theorem 4.2. Let G be a graph with order at least 2k. If |N(u)∩N(v)|≥k + 1 for each pair u,v of nonadjacent vertices, then G isλ_k-connected andλ_k(G)≤ξ_k(G).Definite. Let H₁ be a graph with order (?) + i and H₂ be a graph with order (?) - i for 0≤i≤k - 1. We define a graph family G₁ containing |N(u)∩V(H₂)|≥1 and satisfing |[H₁,H₂]|≤(?) + k - 1, |N(u)∩V(H₂)|≥1 for each vextex u∈V(H₁) and |N(v)∩V(H₁)|≥1 for each vextex v∈V(H₂).Theorem 4.3. Let G be a graph with order n(n≥2k) and G (?) G₁. If |N(u)∩N(v)|≥k+1 for each pair u,v of nonadjacent vertices andξ_k(G)≤(?) + k, then G isλ_k-optimal.Theorem 4.4. Let G be a graph with order n(n≥2k) and F_k be an arbitrary connected subgraph of order k. If |N(u)∩N(v)|≥k +1 for each pair u, v of nonadjacentvertices, and if d(x)≥(?) - k + 2s - 1 for each x∈V(G)\V(F_k) haing exactly s(2≤s≤k) neighbor in F_k, then G isλ_k-optimal.In the fifth chapter, we will show some sufficient conditions for graphs to beλ_k-optimalby using degree sum of two vertices:Theorem 5.1. Let G be aλ_k-connected graph of order n with k≤δ+ 1. If G satisfies the following two conditions, then G isλ_k-optimal:(a) d(x) + d(y)≥2(?) + 2s - 5 for each pair x,y∈V(G) with d(x,y) = k-s + 1, where k - 1≥s≥1;(b) if there exists a connected subgraph F_k with order k such that z is adjacent to every vertex in F_k, then d(z)≥(?) + k - 1. Theorem 5.3. Let G be aλ_k-connected graph of order n with k≤δ+ 1. If G satisfies the following two conditions, then G is super-λ_k:(a) d(x)+d(y)≥2(?) + 2s-3 for each pair x, y∈V(G) with d(x, y) = k - s + 1≥2, where s≥1;(b) if there exists a connected subgraph F_k with order k such that z is adjacent to every vertex in F_k, then d(z)≥(?) + k.In the sixth chapter, we will show relationship betweenλ_k-optimality and super-λ_k-i-connectedness.Theorem 6.1. Let k be a positive integer. If G is aλ_k-optimal graph withδ≥2k - 1, then G is super-λ_k-i for i = 1,2,..., k - 1.