Properties Of The K-restricted Edge Connectivity Of Graphs

With the rapid development of science and technology, the relationship between man and networks becomes more and more closely. The various researches about net-works have attracted increasing attention, and the research about reliability and fault-tolerability of networks has been one of the focal points of worldwide attention. The design and analysis of reliable large-scale networks typically involve some type of graph theoretic model, and the underlying topology of an interconnection network is usually modeled by a graph in which the vertices and edges represent the nodes and links. As is known to all, the traditional edge-connectivity can be used for measures of networks, but this important parameter fails to compare the reliability of graphs with the same edge-connectivity. For further study, F.Harary proposed the concept of conditional connectivity in 1983, and opened up a new way in this research field. Since then, the analysis of reliability and fault-tolerability of networks developed rapidly and became a hot research topic in graph theory.The design and analysis of reliable large-scale networks typically involve such a graph model G=(V,E) in which vertices, are reliable while edges may fail independently with the same probabilityρ∈(0,1). Ifεis the total number of edges in Gr and Ci denotes the number of edge disconnecting sets of size i, then the probability that G is disconnected can be expressed as It follows easily that the reliability of G is 1-P(G,p). Clearly, the smaller P(G,ρ) is, the more reliable the network is. In order to determine the reliability, we" should deter-mine all the coefficients Gi. However, J.S.Proven and M.O.Ball have shown that it is NP-hard. To measure the reliability of networks more accurately, A.H.Esfahanian and S.L.Hakimi proposed the concept of restricted edge-connectivity. Furthermore, Q.L.Li and Q.Li proposed the concept of super restricted edge-connectivity. So far, there have been many extensive researches in this field. In this paper, we mainly continue to discuss the properties of restricted edge-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. Let G=(V,E) be a simple, connected graph with vertex set V(G) and edge set E(G), and let n(G)=|G| denote the order of G. For a vertex v∈V(G) and every nonnegative integer r≥0,Nr(v)= {w∈V(G):d(w,v)=r} denotes the neighborhood of v at distance r. Observe that N0(v)={v}.When r=1 we put simply N(v) instead of N1(v),N[v]=N(v)∪{v}. Gen-erally, for a connected graph G with order n(≥2k), an edge set U is called a k-restricted edge cut of G if G-U is disconnected and every component of G-U has at least k vertices. The k-restricted edge connectivity of G is denoted byλk=λk(G)=min{|U|:U is a k-restricted edge cut of G}. A minimum k-restricted edge cut is called aλk-cut. A connected graph G is calledλk-connected ifλk(G) exists. For a subgraph F of G, we denote by (?)(F) the set of edges with one end in F. Letξk=ξk(G)=min{(?)(F):F is a connected subgraph with order k of G}. Simplyλ2{G),ξ2(G) asλ'(G),ξ(G), whereξ(G) is called minimum edge degree. Ifλk(G)=ξk(G), then G isλk-optimal. Furthermore; G is called a super-λk graph, if everyλk-cut of G isolates one connected subgraph of order k. Clearly, if.G is a super-λk graph, thenλk(G)≥ξk(G). Thus ifλk(G)≤ξk(G), then G must be aλk-optimal graph. However the converse is not true.In the second chapter, we mainly discuss the neighborhood intersection condition for graphs to be optimal and super, and have the following results:Theorem 2.1.1 Let G be a connected graph with order n(≥4),which is different from Kn/22 and／K2,n-2 for all n≥6.If(a) |N(u)∩N(v)|≥2 for all pairs u,v of nonadjacent vertices such that neither u nor v lies on a triangle, and(b) |N(u)∩N(v)|≥4 or G[N(u)∩N(v)](?)K3 for all pairs u,v of nonadjacent vertices with the property that u or v lies on a triangle,then G is super-λ'.Where Kn/22 denote any(n/2+1)-regular graph obtained by joining two copies of the complete graph Kn/2 with n additional edges.Theorem 2.2.1 Let G be a connected graph with order n(≥6),and satisfying |N(u)∩N(v)|≥2 for all pairs u,v of nonadjacent vertices.If(a) |N(u)∩N(v)|≥3 when u or v lie on K4-e or induced 4-cycle,(b) |N(u)∩N(v)|≥5 when u or v lie on K4,then G isλ3-optimal.Theorem 2.2.2 Let G be a connected graph with order n(≥6),if |N(u)∩N(v)|≥5 or G[N(u)∩N(v)](?)K4 for all pairs u,v of nonadjacent vertices,then G isλ3-optimal.In the third chapter,we mainly study some sufficient conditions for graphs to be optimal and super by using subgraph conditions which contain the neighborhood inter-section,the edge degree and the degree condition.We obtain the results as follows:Theorem 3.1.3 Let G be a connected graph with order n(≥4),and different from G6,3, G8,4 and G5,3,If |N(u)∩N(v)|≥3 for all pairs u,v of nonadjacent vertices and then G is super-λ'.Theorem 3.1.4 Let G be a connected graph with order n(≥4),and satisfying |N(u)∩N(v)|≥3 for all pairs u,v of nonadjacent vertices.If for each triangle there exists at least one vertex v such that then G is super-λ'Theorem 3.2.1 Let G be a connected graph with order n(≥6), and different from G5,3 and Gi,4, i=4,6,7,8. If |N(u)∩N(v)|≥3 for all pairs u, v of nonadjacent vertices and then G isλ3-optimal.Where the definition of graph Gi,j can be found in the text.Theorem 3.2.2 Let G be a connected graph with order n(≥6), and satisfying |N(u)∩N(v)|≥3 for all pairs u,v of nonadjacent vertices. If for each triangle and induced 4-cycle there exists at least one vertex v such that then G isλ3-optimal.In the fourth chapter, we mainly give a sufficient condition for a graph to be super-λ' in terms of diameter and girth. We have the following result:Theorem 4.1 Let G be a connected graph with order n(≥4), minimum degreeδ≥3 and diameter D≤g-2. Then G is super-λ' if D=g-2 and one of the following assertions holds.(ⅰ) All pairs u, v of vertices at distance d(u, v)=g-2 are such that neither u nor v lies on a cycle of lenth g.(ⅱ) |N[(g-2)/2](u)∩N[(g-2)/2](v)|≥3 for all pairs u, v of vertices at distance d(u, v)= g-2.