| 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 very active at home and abroad. As we know, edge connectivity plays an important role in the connectivity of graph. But the concept of the classical edge connectivity has some obvious deficiencies. Firstly, even two graphs with the same edge 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, 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 the development in more than twenty years, the contents in conditional edge connectivity become richer and more specific, including super edge connectivity, extra edge connectivity, restricted edge connectivity, and so on.The design and analysis of reliability and fault-tolerability of large-scale networks typically involve some types of graph theoretic model, one important model is a graph such as:Assume that all vertices of G= (V,E) are perfectly reliable and all edges fail independently, with the same probability p∈(0,1). The number of edge cuts of size i is denoted by Ni(G). Then the probability R(G,p) of G being connectedness is given by R(G,p)=1-(?) Ni(G)pi(1-p)ε-i, i=λ(G) hereε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 Ni(G) of a graph. The restricted edge connectivity was proposed by Esfahanian and Hakimi. This concept can reflect more connected properties of graphs that classical concept can not reflect. Furthermore, Q.L.Li and Q.Li proposed the concept of super restricted edge connectivity. 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, terminolo-gies and symbols which will be used in this paper. In the meantime, we also give some related research background and some known results. Let G= (V,E) be a finite, simple, connected graph with vertex set V(G) and edge set E(G), and let n(G)=|G|denote the order of G. For X C V(G), let G[X] be the subgraph induced by X,X= V(G)-X. For A,B∈V(G), let [A, B] be the set of edges with one vertex in A, and the other vertex in B. The edge cut S is called a k-restricted edge cut of G if every component of G-S has at least k vertices. The k-restricted edge connectivity of G is denoted byλk=λk(G)=min{|S|:S 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 number of set of edges with one end in F. Letξ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 may not be true.In the second chapter, we will give two sufficient conditions for a graph to be super-λ' by using the degree, and have the following results:Theorem 2.2 Let G be a graph with order n, andδ(G)≥3. If G satisfies the following conditions, then G is super-λ'.(a) For each edge, there exists one vertex v such that d(v)> [n/2],(b) for each triangle, there exists one vertex v such that d(v)≥[n/2]+2,(c) if d(u)≤[n/2]-1,d(v)≥[n/2],then uv∈E(G). Theorem 2.3 Let G be a graph with order n, andδ(G)≥3. If(a) |N(u)∩N(v)|≥2 for all pairs u,v of nonadjacent vertices in G,(b) for each triangle, there exists one vertex v such that d(v)≥[n/2] + 2,(c) for each induced 4-cycle and K4-, there exists at most one vertex v such that d(v)≤[n/2] - 1, thenG is super-λ'. Where K4- denote any graph obtained by deleting one edge from K4.In the third chapter, we mainly study some sufficient conditions for graphs to be super-λ3 by using subgraph conditions, and have the following results:Theorem 3.3 Let G be a graph with order n(≥6). If(a) |N(u)∩N(v)|≥4 for all pairs u, v of nonadjacent vertices in G,(b)ξ3(G)≤[n/2] + 4, then G is super-λ3 or G∈G1∪G2.Where the definition of Gi(i = 1, 2) can be found in the text.Theorem 3.4 Let G be a graph with order n(≥6). If(a) |N(u)∩N(v)|≥4 for all pairs u, v of nonadjacent vertices in G, specially, |N(u)∩N(v)|≥5 where u or v lie on K4-,(b) for each triangle and induced 4-cycle, there exists one vertex v such that d(v)≤[n/2] + 3, then G is super-λ3 or G∈G1∪G2.In the fourth chapter, we mainly study some sufficient conditions for graphs to beλ4-optimal and super-λ4 by using subgraph conditions which contain the maximum de-gree of two vertices, the neighborhood intersection,ξ4 and the degree, we obtain the results as follows:Theorem 4.1.4 Let G be a connected graph with order n(≥11). Then G isλ4-optimal if(a) max{d(x),d(y)}≥[n/2] + 5 - 2m(m = 2,3,4) for each pair x,y∈V(G) with d(x, y) = m, and(b) for each subgraph K5 of G, there exists one vertex v with d(v)≥[n/2] + 3. If d(·) is changed by d(·) - 1 and the above conditions hold, then G is super-λ4.Theorem 4.2.1 Let G be a graph with order n(≥11). If (a) |N(u)∩N(v)|≥4 for all pairs u,v of nonadjacent vertices in G(b)ξ4(G) [n/2] + 6, then G isλn-optimal or G∈G*.Theorem 4.2.3 Let G be a graph with order n(≥11). If(a) |N(u)∩N(v)|≥5 for all pairs u, v of nonadjacent vertices in G(b)ξ4(G) [n/2] + 8, then G is super-λ4 or G∈G3∪G4∪G5.Where the definition of G*, Gi(i = 3, 4, 5) can be found in the text.Theorem 4.3.3 Let G be a connected triangle-free graph with order n(≥12). If d(x)≥[(n + 2)/4] + 3 for all vertices x∈V(G) with at most one exception, then G isλ4-optimal.Theorem 4.3.4 Let G be a connected triangle-free graph with order n(≥12). If .d(x)≥[n/4] +4 for all vertices x∈V(G) with at most one exception, then G is super-λ4.In the fifth chapter, we mainly discnss the neighborhood intersection condition for a bipartite graph to be optimal and super, we have the following results:Theorem 5.1.1 Let G be a connected balanced bipartite graph with order n(≥4). Then G is super-λ' if d(x)≥[n/4] + 3 for all vertices x∈V(G) with at most one excep-tion in both X and Y.Theorem 5.2.2 Let G be a balanced bipartite graph with order n(≥6). Then G isλ3-optimal if d(x)≥[n/4] + 3 for all vertices x∈V(G) with at most one exception in both X and Y, and |N(u)∩N(v)|≥1 for all pairs u,v in the same part.Theorem 5.3.2 Let G be a connected bipartite graph with order n(≥11). Then G isλ4-optimal if(a) max{d(x),d(y)}≥[(n + 2)/4]+ 4 for each pair x,y∈V(G) with d(x,y) = 2,(b) max{d(x),d(y)}≥[(n + 2)/4] + 1 for each pair x,y∈V(G) with d(x, y) = 3 or 4. If d(·) is changed by d(·) - 1 and the above conditions hold, then G is super-λ4. |
PDF Full Text Request