The Lower-order Restricted Edge-connectivity Of Graphs

With the development of social economy,science and technogy,the relationship be-tweenman and networks becomes more and more closely.Naturally,the research about the reliability and tolerability of networks is very active at home and abroad these years. As we know, edge connectivity plays an important role in the connectivity of graph. But the classical concept of the edge connectivity has three obvious deficiencies. Firstly, even two graphs with the same 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 A disconnecting edges. Thirdly, the shortcoming of using them as measures of fault tolerrance is that it is tacitly assumed that all elements in any subset of G can potentially fail at the time. Consequently, to compensate for these shortcomings, it seems natural to generlize the notion of classi-cal edge connectivity. Since Harary proposed the concept of conditional connectivity in 1983, after about twenty years development, the contents in conditional connectiv-ity become more rich and specific, including super connectivity, extra edge connectivity, restricted edge connectivity, and so on.The design and analysis of reliable large-scale networks typically involve some types of graph theoretic modle. There are a variety of theoretical problems that arise depending on the exact network reliability modle that is used. One important modle is a network of such as:Assume that all vertices of G=(V,E) are perfectly reliable and all edges failed independently.with the same probability p∈(0.1). denote by Ni(G) the number of edge cuts of size. Then the probability R(G,p) of G being connectedness is gave by 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. Bauer et al.defined that a graph G isλ-optimal ifλ(G)=δ(G), and G is super-λif every minimum edge cut of G isolates one vertex.The restricted edge connectivity was proposed by Esfahanian and Hakimi. The restricted edge connectivity provides a more accurate measure of fault-tolerance of net-works than the classical edge connectivity. An edge set U of G is called a restricted edge cut if G-U is disconnected and every component of G-U contains no iso-. lated vertex. If such an edge cut exists, then the restricted edge connectivity of G, denoted byλ'(G), is defined as the cardinality of a minimum restricted edge cut, and G is called A'-connected. Esfahanian and Hakimi showed that each connected graph G of order n≥4 except a star K1,n-1 is A'-connected and satisfiesλ'(G)≤ξ(G), whereξ(G)=min{dG(u)+dG(v)-2:uv∈E(G)} is the minimum edge degree of G. G isλ'-optimal ifλ'(G)=ξ(G). Moreover G is super-A'if every minimum restricted edge cut of G isolates an edge.Let k be a positive integer. For a connected graph G=(V,E), an edge set U C E is a k-restricted edge cut if G-U is disconnected and every component of G-U has at least k vertices. The k-restricted edge connectivity of G, denoted byλk(G), is defined as the cardinality of a minimum k-restricted edge cut, and G is calledλk-connected. k-restricted edge connectivity is an important parameter in measuring the reliability and fault tolerance of networks. Letξk(G)=min{(?)(F):F is a connected subgraph of G,|F|=k}, where (?)(F) denotes the number of edges with one end in F exactly. It has been shown thatλk(G)≤ξk(G) holds for many graphs. G isλk-optimal ifλk(G)=ξk(G).Moreover G is super-λk if every minimum k-restricted edge cut of G isolates one connected subgraph F of order k.This thesis consists of five chapters.In Chapter 1, a survey on the application background and the researeh advance of k-restricted edge-eonneetivity 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,firstly,the optimally and super restricted edge connectivity of graphs are studied.Fan-type conditions for general graphs,bipartite graphs are presented,and then the Nordhaus-Gaddum-type conditions for restricted edge connectivity of graphs are studied.Theorem 2.5.If G is aλ'-connected graph that satisfies the following two condi-tions,then G isλ'-optimal.(a)max{d(x),d(y)}≥「n(G)/2」-1for each pair x,y∈V(G)with d(x,y)=2,and(b)for each triangle T of G,there exists at least one vertex v∈V(T)such that d(v)≥「n(G)/2」+1.Theorem 2.8.Let G be a connected bipartite graph with order n(G)≥4.If max{d(x),d(y)}≥「(n(G)+2)/4」+1 for each pair x,y∈V(G)with d(x,y)=2,then G isλ'-optimal.Theorem 2.12.Let G be a connected graph with order n(G)≥4.If G satisfies the following two conditions,then G is super-λ'.(a)max{d(x),d(y)}≥「n(G)/2」for each pair x,y∈V(G)with d(x,y)=2,and(b)for each triangle T of G,there exists at least one vertex v∈V(T)such that d(v)≥「n(G)/2」+2.Theorem 2.15.Let G be a complete bipartite graph KT,s with 2≤r≤s.then(a)λ'(G)+λ'(G)=r+s-2,(b)ξ(G)+ξ(G)=3r+s-6,(c)λ'(G)+λ'(G)≥min{ξ(G),ξ(G)}+2.In Chapter 3,we will show some sufficient conditions for graphs to beλ4-optimality and super-λ4 by using degree sum of two vertices.Theorem 3.5.Let G be a connected graph with n≥11.Then G isλ4-optimal if the following four conditions hold:(a)d(x)+d(y)≥2「n/2」+1 for each pair x,y∈V(G)with d(x,y)=2,(b)d(x)+d(y)≥2「n/2」-3 for each pair x,y∈V(G)with d(x,y)=3,(c)d(x)+d(y)≥2「n/2」-7 for each pair x,y∈V(G)with d(x,y)=4,and(d)for each subgraph K5 of G,there exists at least one vertex v with d(v)≥「n/2」+3.Collorary 3.6 Let G be a connected and K5-free graph with n≥11.Then G isλ4-optimal if the conditions(a),(b),(c)of Theorem 3.4 hold.Theorem 3.7.Let G be a connected graph with n≥11.Then G is super-λ4 if the following four conditions hold:(a)d(x)+d(y)≥2「n/2」+3 for each pair x,y∈V(G)with d(x,y)=2,(b)d(x)+d(y)≥2「n/2」-1 for each pair x,y∈V(G)with d(x,y)=3,(c)d(x)+d(y)≥2「n/2」-5 for each pair x,y∈V(G)with d(x,y)=4,and(d)for each subgraph K5 of G,there exists at least one vertex v with d(v)≥「n/2」+4.Theorem 3.8.Let G be a connected bipartite graph with n≥11. Then G isλ4-optimal if the following three conditions hold:(a)d(x)+d(y)≥2「(n+2)/4」+5 for each pair x,y∈V(G)with d(x,y)=2,(b)d(x)+d(y)≥2「(n+2)/4」+1 for each pair x,y∈V(G)with d(x,y)=3,(c)d(x)+d(y)≥2「(n+2)/4」-1 for each pair x,y∈V(G)with d(x,y)=4.Theorem 3.9.Let G be a connected bipartite graph with n≥11.Then G is super-λ4 if the following three conditions hold:(a)d(x)+d(y)≥2「(n+2)/4」+7 for each pair x,y∈V(G)with d(x,y)=2,(b)d(x)+d(y)≥2「(n+2)/4」+3 for each pair x,y∈V(G)with d(x,y)=3.(c)d(x)+d(y)≥2「(n+2)/4」+1 for each pair x,y∈V(G)with d(x,y)=4.In Chapter 4,we obtain the sufficient conditions for minimally 4-restricted edge- connected graphs to be optimal by characterizing some structure properties of aλ4-connected graph G withλ4(G)<ξ4(G),Definition:A graph G is called minimally 4-restricted edge connectivity (mini-mallyλ4-graph for short) ifλ4(G-e)=λ4(G)-1 for each edge e∈E(G).Theorem 4.6. The minimally 4-restricted edge-connected graphs areλ4-optimal except 3-regular graphs with girth g(G)=5,each edge incident with a 5-cycle and being super-λ5.In Chapter 5,we mainly continue to discuss the related properties of k-restricted connectivity on the basis of previous work.