| Usually the edge-connectivity and super edge-connectivity of graphs are used for measuring the reliability of networks. However, these parameters fail to compare the reliabilityof graphs with the same edge-connectivity and super edge-connectivity. Therefore,in order to more accurately measure the reliability, the concept m-restricted edgeconnectivityis proposed. Let m be a positive integer, an edge-cut S of a connected graph G is called an m-restricted edge-cut, if each component of G- S contains at least m vertices, and the minimum cardinality of all m-restricted edge-cuts is called the m-restricted edge-connectivity of G, denoted byλm(G). Usually, when m = 2,λ2(G) is called restricted edge connectivity of G, denoted byλ'(G). G is calledλm-connected ifλm(G) exists. At present, studies on m-restricted edge connectivity mainly focus on discussing the existence of m-restricted edge connectivity and its upper bound, calculatingthe m-restricted edge connectivity of some special graphs or networks, and searching for graphs with maximally m-restricted edge connectivity and fewer minimumm-restricted edge-cuts. Letξm(G) :=min{|[X,X]|: X(?) V(G),|X| = m, and G[X] is connected}. An m-restricted edge-cut S = [X, X] is called trivial if |X| = m or |X|= m. Aλm-connected graph G withλm(G)≤ξm(G) is said to be optimally m-restricted edge connected, for shortλm-optimal, ifλm(G) =ξm(G), and to be super m-restricted edge connected, for short super-λm, if every minimum m-restricted edgecutof G is trivial. Generally,λm-optimal graphs and super-λm graphs have higher reliability.This thesis consists of five chapters. In Chapter 1, a survey on the application background and the research advance of m-restricted edge-connectivity of graphs are given; then, some definitions and notations used in this thesis are introduced; finally, the main results acquired in this thesis are listed.In Chapter 2, a general sufficient condition for a graph G satisfyingλm(G)≤ξm(G) is presented. Previous studies showed that aλm-connected graph G has the propertyλm(G)≤ξm(G) for m≤3, but for m≥4, Bonsma et al. pointed out that the inequalityλm(G)≤ξm(G) is no longer true in general, and in 2007 Ou showed that aλ4-connected graph G with order at least 11 has the propertyλ4(G)≤ξ4(G). In this chapter, by characterizing some structure properties of aλm-connected graph G withλm(G) >ξm(G), we obtain not only the above Ou's result but the result that aλm-connected graph G with order greater than m(m - 1) satisfies the inequality λm(G)≤ξm(G) for m≥5. At last, by constructing some examples, we testify that our conditions are best possible.In Chapter 3, the optimally restricted edge connectivity of graphs is studied. Sufficient conditions for general graphs, bipartite graphs, and for graphs with diameter 2, to beλ'-optimal are presented, respectively, and at the same time by constructing examples to illuminate that these conditions cannot be weakened. In addition, the results acquired in this chapter improve the Hellwig and Volkmann's in 2004 and 2005, and the results for graphs with diameter 2 generalize the Wang and Li's in 1999.In Chapter 4, the super restricted edge connectivity of graphs is discussed. We present sufficient conditions for general graphs, bipartite and triangle-free graphs, and for graphs with diameter 2, to be super-λ', and by means of examples, indicate our results are best possible. In this chapter the results we acquired generalize the Wang and Li's in 2001. In addition, as far as the super-λ' connectivity for triangle-free graphs with diameter 2 is concerned, we obtain a corollary similar to the Wang and Lin's result in 2007, and generalize the Fan's in 2003.In Chapter 5, we discuss theλ3-optimality and super-λ3 connectivity of graphs. Firstly, the relations between theλ3-optimal,λ'-optimal, and super-λ' are discussed. Then, sufficient conditions for general graphs, bipartite graphs and triangle-free graphs, and for graphs with diameter 2, to beλ3-optimal and super-λ3 are presented, respectively.Also in this chapter we construct examples to show that these conditions cannot be weakened. Finally, the structure property of a super-λm graph G with minimum degreeδ≥2m which is not complete graph is obtained: the induced subgraph G[M] of minimum degree vertices set M of graph G contains no complete subgraph Kδ-m+1. In this chapter, we generalize the Ou's result on theλ3-optimality of triangle-free regulargraphs to general graphs. Also, our results generalize the Wang's in 2006 on theλ3-optimality and super-λ3 connectivity for graphs with diameter 2.
|
PDF Full Text Request