The K-restricted Edge Connectivity Of Graphs To Be Optimal And Super-connected

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.If not explicity, all graphs considerd in this paper are simple and connected. 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ρ. Let G be a network model, denoted by C_h the number of its edge cuts of size h. If G 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. But unfortunately, Provan and Ball shows in [1] 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. For further study, Esfahanian and Hakimi proposed the concept of restricted edge connectivity in [14]. For more accurate results, Fabrega and Fiol improved the concepts to k-restricted edge cut and k-restricted edge connectivity in [16]. And the study of it have gotten many achievements. The first chapter of this paper, we give a brief introduction about the basic conceps, terminologies and symboles which will be used in this paper. In the meantime we also give some related research backgrounds and some known results. Let G = (V, E) be a graph with vertex set V(G) and edge set E(G) and note n(G) = |V|. For X (?) V(G), let G[X] be the subgraph induced by X, (?) = V(G) - X, and [X, (?)] be the set of edges in G with one end in X and the other in (?). If G is a connected graph with order at least 2k and S (?) E(G), such that G - S is disconnected, and each component of G - S consists of at least k vertices, then we call it a k- restricted edge cut or R_k- edge cut for short. The minimum cardinality over all R_k^- edge cut in G is called k-restricted edge connectivity, denoted byλ_k(G). Clearly,λ(G) =λ₁(G)≤λ₂(G)≤…≤λ_k(G). A connected graph G isλ_k-conected,ifλ_k(G) exists. Let X∈V(G),α(G) = |[X,(?)]|. Noteξ_k(G) = min(α(X) : |X| = k and G[X] is connected}. we can easily to say thatξ₁(G) =δ(G) withδ(G) is the minimum degree of G. We call a graph G isλ_k^-optimal, ifλ_k(G) exists andλ_k(G) =ξ_k(G). Also we call a graph G is super-λ_k, if every R_k^- edge cut isolated a connected subgraph of order k.Harary gave the definition of generalized restricted edge connectivity at the first time. Generally, for two integer p, q≥1, a connected graph G isλ_p,q^-connected if it contains an edge cut whose removal results in two components containing at least p and at least q vertices. Rautenbach and Volkmann gived us some properties aboutλ_2,q^-connected in [2].In the second chapter, we are mainly to think about the properties ofλ_3,q^-connected, which make the main rusult in [26] to become the corollary of the main results of this chapter.In the thrid chapter, we are mainly to study Afc-optimal and super-λ_k with k = 3,4 of the graph. We will give: a minmurn degree for graphs to beλ_3^-optimal and super-λ₂ connected; a minmum degree for graphs to beλ_4^-0optimal and super-λ₃ connected and a sum degree condition for graphs to beλ_4^-optimal and super-λ₄ connected.In the fourth chapter we will give a degree sequence for graphs to beλ_k^-optimal.In this paper we have the following theorems:Theorem 2.3 Let n, q be two integers such that n≥max{7, q + 3} and q≥3,(i)a connected graph G of order n≥2q - 1 is notλ_3,q^-connected if and only if G∈W_n^*.(ii)a connected graph G of order n = 2q - 2 is notλ_3,q^-connected if and only if(iii)a connected graph G of order n = 2q - 3 is notλ_3,q^-connected if and only ifG∈{W_n^*,S^*(q-1,0,q-2),S^*(q-2,1,q-2),R^*(q-2,1,q-2)}.and the new-constructed graphs define as Definition 2.1 , 2.2.Corollary 2.6 For an integer t≥1 and 0≤r≤5, let q = 6t + r. If G is a connected graph of order n≥q + 3 that contains a cycle C of length l with l≥3t + 5, then G isλ_3,q^-connected.Theorem 3.1.5 Let G be a connected graph of order n≥10 and letδ(G)≥[n/2] - 2, If for each 4-cycle C there exists at least one vertex w such that d(w)≥[n/2] + 2, then G isλ_3^-optimal. Furthermore, if for each triangle T there exists at least one vertex v such that d(v)≥[n/2], then G is super-λ₂ connected.Theorem 3.2.4 Let G be aλ₄connected graph of order n≥11 and letδ(G)≥[n/2] - 3. If for each induced 5-cycle and each sticking graph of two triangle there exist at least one vertex u except the sticking vertexs such that d(u)≥[n/2] - 1, for each induced 5-cycle there exists at least one vertex v such that d(v)≥[n/2] + 1 and for each triangle K₄ - e there exists at least one vertex w such that d(w)≥[n/2], then G isλ_4^-optimal. Furthermore, if n≥12, then G is super-λ₃ connected.Theorem 3.3.2 If G be aλ_4^-connected graph of order n≥11 satisfying the following three conditions, then G isλ_4^-optimal.(i)For two vertices x and y with d(x, y) =t such that d(x)+d(y)≥2[n/2] - 2t+1(t = 2,3,4),(ii)for each induced 4-cycle there exists at least one vertex u such that d(u)≥[n/2] +1,(iii)for each triangle K₄ - e there exists at least one vertex v such that d(v)≥[n/2]+3.Theorem 3.3.5 If G be aλ_4^-connected graph of order n≥11 satisfying the following three conditions then G is super-λ₄ connected.(i)For two vertices x and y with d(x, y) = t such that d(x)+d(y)≥2[n/2] -2t+3(t= 2,3,4), (ii)for each induced 4-cycle there exists at least one vertex u such that d(u)≥[n/2]+2,(iii)for each K₄ - e there exists at least one vertex v such that d(v)≥[n/2] + 4.Theorem 4.3 Let G = (V, E) is aλ_k^-connected graph of order n with girth g > k + 1, if for every subgraph H of G such that |E(H)|≤|V(H)|²/g,λ_k(G)≤ξ_k(G) and G has degree sequence d₁≥d₂≥…≥d_n =δsatisfying:then G isλ_k^-optimal.