The Research About Edge-connectivity And Connectivity Of Graphs

Graph theory is an ancient but quite active subject, and is also a very practical sub-ject. As an important branch of combinatorial mathematics and discrete mathematics, it’s the important mathematical tools of studying the natural sciences, engineering tech-nology and so on, the application is quite extensive. In the era of economic development, the relationship with computer science and network theory also becomes more and more closely. The edge-connectivity problem of graphs in graph theory stems from the large-scale network design and reliability analysis, and has very wide range of applications in practical problems. Now, edge-connectivity problem has become a hot research field in graph theory.The analysis for multiprocessors interconnection network usually involves some type of graph theoretic model, using vertexes and edges of graph instead of nodes and links of network in order to constitute the interconnected network topology. An important mathematic model is to abstracted as undirected graph G=(V,E), in which the vertex set of G represent all processors, and the edge set represent communication links between processors in the system. So the performance of the network topology can be described through the nature of the graph. When studying such model, we usually assume that all nodes never fail, but links between nodes that is edges can independently fail with equal probability ρ∈(0,1). Then the probability R{G, p) of G being connectedness can be expressed as here ε is the number of edges of G, and λ(G) is the edge-connectivity of G, the num-ber of edge cuts of size i is denoted by Ci(G). Obviously, the bigger R(G,ρ) is, the better the reliability of network is. If we can calculate all the coefficients Ci(G)(i=λ(G),λ(G)+1,...,ε), then the reliability of network is determined. But for a general graph G, Provan and Ball[6]proved that it is N P-hard to calculate R(G, p) in1983.An important indicator for network is to expect its reliability as good as possible, and using graph theory terms, is to hope the edge-connectivity of the graph as large as possible. Consequently, edge-connectivity becomes a classic parameter in measur-ing the connectivity of graph, and also becomes an important parameter in reflecting the reliability of network. But to precisely describe the connectivity of graphs, classic edge-connectivity has some deficiencies. Firstly, even two graphs with the same edge-connectivity may have different reliability; secondly, we can’t differentiate between the different types of graph which result from removing A disconnecting edges; thirdly, it is tacitly assumed that all elements in any subset of a graph can potentially fail at the same time. In order to better describe the connectivity of graph, Harary[7] proposed the con-cept of conditional edge-connectivity in1983, opening up a new path for the research of this field. Sequentially, the analysis about the reliability and fault-tolerability of networks rapidly developed the hot topic in the research of graph theory. For the case that many new parameters have been proposed, which including maximally edge-connectivity, super edge-connectivity, restricted edge-connectivity and local-edge-connectivity. At present, we have extensive and thorough research for this field. In this paper, we will continue to discuss the properties of edge-connectivity and local connectivity on the basis of previous work.In this paper, we consider finite and simple digraphs. In the first chapter, we mainly introduce some related research background, the basic concepts, terminologies and sym-bols which will be used in this paper, and some known results.The edge-connectivity of graph G is λ{G)=min{|(X,Y)|:φ≠X∈V(G),Y=V(G)\X}, a minimum (X, Y) is called a A-cut of G. Bauer and so on also proved that the bigger X(G) is, the better the reliability of network is. Thus we hope A(G) as large as possible in network design. For arbitrary digraph G, it is clearly that λ(G)≤δ(G), so we call G maximally edge-connected also known as λ-optimal when satisfying λ(G)=δ(G).In order to more exactly describe the reliability of network,the concept of local-edge-connectivity is proposed.The local-edge-connectivity of two vertices u and v in graph G is denoted by λ(u,v)=min{|(x,y)|:u∈X∈V(G)\{v),Y=V(G)、X}.A minimum(X,Y) is called a λ(u,v)-cut of G.Clearly；λ(u,v)≤min{d(u),d(v)),so we call G maximally local-edge-connected,for short mlec when λ(u,v)=min{d(u),d(v)} for arbitrary vertices u and v.A.Holtkamp proposed the concept of diamond-free on2007.The graph obtained from a complete graph of4by removing an arbitrary edge is called a diamond.A graph is then called diamond-free,if it contains no diamond as a(not necessarily in-duced)subgraph.A.Holtkamp proposed the concept of K2,p-free graph on2011.We call a graph K2,p-free if it contains no complete bipartite graph K2,p as a(not necessarily induced) subgraph.In the second chapter,we mainly discuss the maximally_local-edge-connectivity of K2,p-free graphs,so In the second chapter,we get the following results which are also sufficient conditions:Theorem2.1.4Let G be a K2,p-free graph of order n,and minimum degree δ.if n≤4δ-2p+3,p≥3,and δ≥4p/3,then G is maximally-local-edge-connected.Corollary2.1.5Let G be a K2,p+1-free graph of order n,without induced-C4graph,minimum degree δ.If n≤4δ-2p+1,p≥2,δ≥4(p+1)/3,then G is maximally-local-edge-connected.Corollary2.1.6Let G be a K2,p+1-free graph of order n,without. induced-C4graph,minimum degree δ.If n≤4δ-2p+1,p≥2,δ≥4(p+1)/3,then G is maximally-edge-connected. In the following section,using K2,p+1to restrict the induced-C4-free graph,we can obtain the following results about maximally-edge-connectivity of induced-C4-free graphs.Theorem2.2.1Let G be a connected K2,p+1-free graph of order n without C4as its subgraph,minimum degree δ≥2p and p≥3.If n≤4δ-2p+3,then G be maximally-edge-connectedCorollary2.2.2Let G be a connected graph of order n without C4as its subgraph,minimum degree δ≥6.If n≤4δ+1,then G be maximally-edge-connected.In the third chapter,we mainly discyss the maximally-local-connectivity of K2,p-free graphs,so In the third chapter,we get the following results.Theorem3.1.5Let p be a integer(p≥2),G be a connected K2,p-free graph of order n,minimum degree δ≥2p+m-2/2手,and m∈{0,1,2).If n≤3δ-2p+3+m,then G be maximally-local-connected.Theorem3.2.2If G be a K2,4-free connected graph of order n without C4as its in-duced subgraph,minimun degree δ≥3.If n≤3δ一4,Then G be maximally-connected.In the forth chapter, using the existing theorems have been proved about the maximally-local-edge-connectivity of diamaond-free graphs,using the clique nnmber to restrict the induced-diamond-free graph,we can obtain the following results about the maximally-local-edge-connectivity of induced-diamond-free graph.Theorem4.6Let G be a connected graph of order n without diamond as its induced subgraph,clique number ω(G)≤p,δ≥p≥3.If n(G)≤4δ-2p+5,then G be maximally-local-edge-connected. Corollary4.10Let G be a connected graph of order n without diamond as its induced subgraph, clique number w(G)<p, δ> p>3. If n(G)<4δ-2p+5,then G be maximally-edge-connected.In the fifth chapter, similar to the forth chapter, using the existing theorem have been proved about the maximally-local-connectivity of diamond-free graphs, using the clique mumber to restrict the induced-diamond-free graph, we can obtain the following results about the maximally-local-connectivity of induced-diamond-free graph.Theorem5.6Let G be a connected graph of order n without diamond as its induced subgraph, clique number ω(G)≤p,minimum degree δ≥p≥3. If connectivity κ≤δ,then κ≥4δ-n-2p+6.Corollary5.7Let G be a connected graph of order n without diamond as its induced subgraph, clique number ω{G)≤p,minimum degree δ≥p≥3.If n≤3δ{G)-2p+6,then κ=δ.