|
The High Order Restricted Edge-connectivity of Graphs
|
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.