Study On The Properties Of Edge Connectivity And Vertex Connectivity Of Graphs And Digraphs

In the modern society, the relationship between people’s daily life, work, studyand internet networks of multiprocessor becomes more and more close. The reliabil-ity and fault-tolerability of networks are widely concerned by the society. Naturally,in recent years the research into the reliability and fault-tolerability of networks hasbecome a hot research topic at our country and abroad. When designing andanalyzing the reliability and fault-tolerability of large-scale networks, a very im-portant model is to abstract the topological structure of the network into a graphD=(V, E). Then vertices of D represent processors, and edges express connectedvertices direct communication between the processors. We assume that all verticesdo not fail, and all edges independently fail with equal probability p∈(0,1). Thenthe probability of D being not connected is given by:here m is the number of edges of D, and λ(D) is the edge connectivity of D.The number of edge cuts of size i is denoted by Ci(D)[1]. Take the probabil-ity of D being connected R(D, p)=1P (D, p) to measure the reliability ofthe network. Obviously, the smaller P (D, p) is, the better the reliability of net-works is. To calculate P (D, p) exactly, one need to calculate all the coefcientsCi(D)(i=λ(D), λ(D)+1,, m). But in1983, Provan and Ball[2]proved that itis NP hard to determine all these coefcients. Colbour[3]made further explana-tions for that. There is a similar discussion assuming that all edges do not fail, andall vertices independently fail with equal probability p∈(0,1). As we all know, edge connectivity and vertex connectivity are classic parame-ters in measuring the connectivity of (di-)graphs. But the concept of the classicaledge connectivity or vertex connectivity has some obvious deficiencies when the con-nectivity properties of (di-)graphs are precisely drawn. To begin with, even two(di-)graphs with the same edge connectivity or vertex connectivity can have difer-ent reliability. What’s more, the model is unable to accurately reflect the extent ofdamage of the network caused by the damage of gateway. That is, they do not dif-ferentiate among the diferent types of disconnected (di-)graphs which result fromremoving λ disconnecting edges or κ disconnecting vertexes. Thirdly, it is assumedthat all elements in any subset of D may fail at the same time. To compensate forthese shortcomings, many concepts such as maximally edge connectivity, super edgeconnectivity, maximally local edge connectivity and super local edge connectivityare proposed. Similarly, as to the vertex connectivity, the concepts of maximallyconnectivity, super connectivity and maximally local connectivity occurred. Theseparameters can reflect deeper connectivity properties of (di-)graphs which classical(edge) connectivity can not reflect. In this paper, we continue to discuss the prop-erties of edge connectivity and vertex connectivity of (di)graphs. We will proposethe concept of super local connectivity and discuss its properties.In the first chapter, we give a brief introduction to the basic concepts, termi-nologies and symbols which will be used in this paper. In the meantime, we also givesome related research background and some known results. Let D=(V (D), E(D))be a finite and simple (di-)graph, where V (D) is the vertex set and E(D) is the edgeset. Let n=|V (D)|denote the order of D. For S, T V (D), let (S, T) be the setof edges with the starting vertex in S, and the ending vertex in T. For X V (D),D[X] denotes the sub(di-)graph induced by X. Let X=V (D) X. A digraphwithout any directed cycle of length2is called an oriented graph. A p-diamond isa graph with p+2vertices, where two adjacent vertices have exactly p commomneighbours, and the graph contains no futher edges. A2-diamond is also called adiamond.The edge connectivity of a (di)graph D is defined as λ(D)=min{|(X, Y)|:=X V (D), Y=V (D)\X}, and a minimum (X, Y) is called λ-cut of D. Obviously, λ(D)≤δ(D). A (di)graph is called to be maximally edge connected or simplly λ-opt. if λ(D)=δ(D). If every λ-cut of D consists of edges from or to a vertex,then D is called to be super edge connected or simplly super-λ. For two verticesu and v in a (di-)graph D, the local edge connectivity of u and v is denoted byλ(u, v)=min{|(X, Y)|: u∈X V (D)\{v}, Y=V (D)\X}, a minimum (X, Y)is called λ(u, v)-cut of D. Obviously, λ(u, v)≤min{d+(u), d (v)} for all pairs uand v of vertices in D. We call a (di-)graph D maximally local edge-connected orsimply mlec, when λ(u, v)=min{d+(u), d (v)} for all pairs u and v of vertices inD. If a λ(u, v)-cut consists of edges from u or to v, then it is called to be trivial.D is called to be super local edge connected or simply slec, if every λ(u, v)-cut istrivial.The connectivity of a noncomplete graph G is defined as κ(G)=min{|S|:=S V (G), G S is not connected}, and a minimum S is called minimum cut,orκ-cut. The connectivity of a complete graph G is defined as n(G)1. Obviously,κ(G)≤δ(G). G is called to be maximally connected if κ(G)=δ(G). A κ-cut issaid to be trivial if it consists of edges of some vertex. A graph G is called to besuper-κ, if all its κ-cuts are trivial. The local connectivity κ(u, v) of two verticesu and v in a graph G is the maximum number of internally disjoint u v paths inG. Clearly,κ(u, v)≤min{d(u), d(v)} for all pairs u and v of vertices in G. We calla graph G maximally local connected when κ(u, v)=min{d(u), d(v)} for all pairsu and v of distinct vertices in G.The inverse degree of a digraph without zero degree is defined as R(D)=in the second chapter, we study on the edge-connectivity of digraphsv∈V (D)d(v). Inand oriented graphs with the inverse degree conditions.We first get the inverse degree conditions for the general digraphs to be superedge-connected.Theorem2.1.1Let D be a strongly connected digraph with n≥2. If theminimum degree Where, the definition of D∈Hn,δcan be found in the text.Then,we give the inverse degree conditions for the triangle-free digraphs to besuper edge-connected, and the condition is best possible.Theorem2.2.1Let D be a strongly connected triangle-free digraph withthenAt last, we give the inverse degree conditions for the oriented graphs to bemaximally edge-connected or super edge-connected.Theorem2.3.1Let D be a strongly connected oriented graph with n≥2. Ifthe minimum degreeTheorem2.3.2Let D be a strongly connected oriented graph with n≥2. Ifthe minimum degreeIn the third chapter, we study on the (edge) connectivity of p-diamond-freegraphs and C4-free graphs.In section3.1, we give sufcient conditions for p-diamond-free graphs to bemaximally local-edge-connected and the conditions are best possible in some cases.Theorem3.1.2Let D be a p-diamond-free (p≥2) graph with order n. G ismaximally local edge connected, if n≤4δ2p+1.In section3.2, we give sufcient conditions for C4-free graphs to be maximallylocal-edge-connected.Theorem3.2.1Let G be a C4-free graph with δ≥3and the order n≤4δ1,then G is maximally local edge-connected.In section3.3, we give sufcient conditions for p-diamond-free graphs to besuper local edge connected and the conditions are best possible in some cases.Theorem3.3.1Let G be a p-diamond-free (p≥2) graph with order n andminimum degree δ. G is super local edge connected, if In section3.4, we study on the super connectivity of diamond-free graphs, andhave the following best possible results:Theorem3.4.4Let G be a diamond-free connected graph with order n andminimum degree δ≥3. If G is not super-κ,then κ≥4δ n2. Especially,if δ≥5and G is not super-κ,then κ≥4δ n.Theorem3.4.5Let G be a diamond-free connected graph with order n andminimum degree δ≥3. If n≤3δ3, or if δ≥5, and n≤3δ1, then G is super-κ.In section3.5, we propose the concept of the super local connectivity of agraph.Definition3.5.1Let u, v be two nonadjacent vertices of graph G. S is aκ(u, v)-cut of G. S is called to be trivial, if G S isolates u or v, that is, S=N(u)or S=N(v).Definition3.5.2Let G be a graph. If κG(u, v)-cut is trivial for any twononadjacent vertices u, v∈V (G), and κH(u, v)-cut is trivial for any two adjacentvertices u, v∈V (H), where H=G uv, then G is called to be super localconnected.We study on the super local connectivity of p-diamond-free graphs and givethe following results.Theorem3.5.6Let p≥2be an integer and G be a connected p-diamondfree graph with order n, n≤3δ2p+1,where the definition of H, Gpcan be found in the text.Corollary3.5.7Let p≥2be an integer and G be a connected K2,p-freegraph with order n. If n≤3δ2p+1, then G is super local connected.In the fourth chapter, we get the sufcient conditions for graphs to be superlocal-connected depending on the clique number.Theorem4.6Let p≥2be an integer and G be a graph with order n and clique number then, G is super local connected.