Optimality And Super-connectness Of K-restricted Edge Connectivity In Graphs

Nowadays, in the information age that social economy, science and technology develop rapidly, networks becomes more and more important in every aspects of people's life. In these years, the research on the reliability and fault-tolerability of networks becomes one of the most active research topics at home and abroad. As known to all, edge-connectivity plays a very important role in the connectivity of graphs. In order to depict the connectivity of graphs more precisely, we should generalize the notion of classical edge-connectivity. F.Harary proposed the concept of conditional edge-connectivity in 1983. Having been developed about twenty years, a few conditional edge-connectivity problems with different restrictions have been presented and studied by some scholars. In the studies of big networks design and reliability analysis, restricted edge-connectivity plays an important role and has many applications in real life. Restricted edge-connectivity is a very active research topic in graph theory.When design and analysis.the reliability of large-scale networks, it typically involves some measure standards and types of graph theoretic models. There are many different theoretical problems that arise from the different measure standards and types of graph models. When we measure the networks reliability with the standard of the disconnec-tivity of graphs, one important model is a graph networks such as:a graph G=(V,E). we assumed that the nodes don't fail, meanwhile the edge fails independently and with the same probability. Let p∈(0,1) be the probability of failure. Then the probability that G is disconnected can be expressed as Where e is the total number of edges in G, Ch is the number of edge cuts of size h. Therefore, the reliability of G is 1-P(G,p). Clearly, P(G,p) is smaller, the more re-liabler of G is. Naturally, in order to determine P(G,p) for a given graph G and p, we need to determine all the coefficients Ch. But unfortunathely, J.Proven and M.Ball have shown that the calculation of the coefficients Ch and P(G,p) for an arbitrary graph G belongs to the class of computationally intractable problems known as NP-hard. So A.H.Esfahanian and S.L.Hakimi proposed the concept of restricted edge-connectivity of graphs, when they study the design and reliability analysis of the big networks. This concept can reflect more connected properties of graphs that classical concept can not reflect. J.Fabrega and M.A.Fiol improved the concept to k-restricted edge-connectivity. In this paper, we will mainly continue to discuss some sufficient conditions for graphs to beλk-optimal or super-λk and related properties of restricted edge-connectivity on the basis of previous research and work.In the first chapter, we give some related research backgrounds and some known re-sults. Meanwhile we also give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper.The graphs in this paper are finite, simple, undigraph and connected. Let G=(V, E) be a graph with vertex set V and edge set E, and denote n(G)=|V|.For X (?) V(G), let G[X] be the subgraph induced by X,X=V(G)-X. For A, B C V(G), let [A, B] be the set of edges in with one vertex in A, and the other vertex in B. Denote (?)(X)=|[X, V-X]|.Let k be a positive integer,G be a connected graph of order n(≥2k). An edge set S C E is called a k-restricted edge cut and denoted by Rk-edge cut for short if G-S is disconnected and every component of G-S has at least k vertices. The size of a minimum Rk-edge cut of graph G is called k-restricted edge connectivity, denoted by λk(G),or simplyλk. G is calledλk-connected graph,if G contains Rk-edge cuts.Letξk(G)=min {(?)(X):X(?)V(G),|X|=k,G[X]is connected}.X and X are calledλk-fragments if[X,X]is aλk-cut. Aλk-fragment with minimum cardinality of G is called aλk-atom.The cardinality of aλk-atom is denoted by rk(G).Aλk-connected graph G is calledλk-optimal graph,ifλk(G)=ξk(G).Moreover, G is super-λk connected graph if every minimum k-restricted edge cut of G isolates one connected subgraph of order k,in short,super-λk graph.In the second chapter,we mainly give some sufficient conditions for graphs to beλk-optimal and super-λk(k=2,3).We have some results as follows:Theorem2.1.3 Let p≥3 be an integer,and G be aλ'-connected graph of order n≥4 with clique number w(G)≤p and degree sequence d1≥d2≥…≥dn=δ.If then G is super-λ' graph.Theorem2.2.4 Let G be aλ3-connected graph of order n,satisfys |N(u)∩N(v)|≥1 for all pairs u,v of nonadjacent vertices andξ3(G)≤[n/2].If G satisfys conditions as follows:(a)For each induced 4-cycle there exists at least one vertex w such that d(w)≥[n/2]-1；(b)for each K4-e there exists at least one vertex w such that d(w)≥[n/2]+1；(c)for the vertex w,the one degree vertex of K1,3+e satisfys d(w)≥[n/2]-3, then G isλ3-optimal graph.Theorem2.3.2 Let G be aλ3-connected graph of order n satisfying the conditions as follows:(a)For two vertices x and y with d(x,y)=2 or 3 satisfy max {d(x),d(y)}≥[n/2]-2；(b)for the vertex v,the one degree vertex of K1,3+e satisfys d(v)≥[n/2]-2；(c)for each induced 4-cycle there exists at least one vertex v such that d(v)≥[n/2]；(d)for each K4-e there exists at least one vertex v such that d(v)≥[n/2]+2, then G isλ3-optimal graph.If change d(·)to d(·)-1 and the conditions still hold,then G is super-λ3 graph.In the third chapter,we mainly give two sufficient conditions for bipartite graphs,and obtain the results as follows:Theorem3.1.6 Let G(X∪Y E)be aλ3-connected bipartite graph,andδ(G)≥3. Ifλ3(G)<ξ3(G),then r3(G)≥(ξ3(G)+3)/2.Theorem3.2.4 Let G(X∪Y, E)be a bipartite graph of order n≥6,andξ3(G)≤[n/2].If G has a matching that saturates every vertex in X or every vertex in Y and |N(u)∩N(v)|≥3 for any u,v∈X and any u,v∈Y,then G isλ3-optimal graph.In the fourth chaper,we mainly give some sufficient conditions and related properties for the optimality and super-connectness of k-restricted edge connectivity in graphs.Theorem4.2 Let G be a connected graph of order n≥2k,δ(G)≥k-1,and is not Gm,t*,t=δ(G),then(a)G isλk-optimal graph if and only if either G is nonλk+1-connected graph or G isλk+1-connected graph andλk+1(G)≥ξk(G)；(b)G is super-λk graph if and only if either G is nonλk+1-connected graph or G isλk+1-connected graph andλk+1(G)>ξk(G).The definition of Gm,t* refer to the main text of this paper.Theorem4.4 Let G be a connected triangle-free graph of order n≥2k,andδ(G)≥k-1.If d(x)≥[n+2/4]+(k+(k-2)2)/2 for all vertices x∈V(G)with at most one exception, then G isλk-optimal graph.Theorem4.5 Let G be a connected triangle.free graph of order n≥2k+4,andδ(G)≥k-≥2.If d(x)≥[n+2/4]+(k+(k-2)2)/2 for all vertices x∈V(G)with at most one exception,then G is super-λk graph.Theorem4.8 Let k≥2 be a positive integer.G is aλk-optimal triangle-free graph withδ(G)≥max{3,k-2},if G satisfys d(u)+d(v)≥4k-7 for all pairs u,v of nonad-jacent vertices,then G is super-λk-i graph for i=1,2,…,k-1.