| 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 moreclosely. 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 inpractical problems. Now, edge-connectivity problem has become a hot research field ingraph theory.The analysis for multiprocessors interconnection network usually involves some typeof graph theoretic model, using vertexes and edges of graph instead of nodes and links ofnetwork in order to constitute the interconnected network topology. An important math-ematic model is to abstracted as (undirected or directed) graph D=(V, E), in which thevertex set of D represent all processors, and the edge set represent communication linksbetween processors in the system. So the performance of the network topology can be de-scribed through the nature of the graph. When studying such model, we usually assumethat all nodes never fail, but links between nodes that is edges can independently failwith equal probability ρ∈(0,1). Then the probability R(D, ρ) of D being connectednesscan be expressed as:here ε is the number of edges of D, and λ(D) is the edge-connectivity of D, the num-ber of edge cuts of size i is denoted by Ci(D). Obviously, the bigger R(D, ρ) is, thebetter the reliability of network is. If we can calculate all the coefcients Ci(D)(i= λ(D), λ(D)+1,..., ε), then the reliability of network is determined. But for a generalgraph D, Provan and Ball[1]proved that it is NP-hard to calculate R(D, ρ) in1983.Therefore, Colbour[2]made a further explanation.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 largeas possible. Consequently, edge-connectivity becomes a classic parameter in measur-ing the connectivity of graph, and also becomes an important parameter in reflectingthe reliability of network. But to precisely describe the connectivity of graphs, classicedge-connectivity has some deficiencies. Firstly, even two graphs with the same edge-connectivity may have diferent reliability; secondly, we can’t diferentiate between thediferent types of graph which result from removing λ disconnecting edges; thirdly, it istacitly assumed that all elements in any subset of a graph can potentially fail at the sametime. In order to better describe the connectivity of graph, Harary[3]proposed the con-cept of conditional edge-connectivity in1983, opening up a new path for the research ofthis field. Sequentially, the analysis about the reliability and fault-tolerability of networksrapidly developed the hot topic in the research of graph theory. For the case that manynew parameters have been proposed, which including maximally edge-connectivity, superedge-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 todiscuss the properties of edge-connectivity on the basis of previous work.In this paper, we consider finite and simple digraphs. In the first chapter, we mainlyintroduce some related research background, the basic concepts, terminologies and sym-bols which will be used in this paper, and some known results.We know that edge-connectivity λ(D) plays a key role in the research about thereliability of network. The edge-connectivity of digraph D is λ(D)=min{|(X, Y)|:=X V (D), Y=V (D)\X}, a minimum (X, Y) is called a λ-cut of D. Bauer and so on[4]also proved that the bigger λ(D) is, the better the reliability of network is. Thus we hopeλ(D) as large as possible in network design. For arbitrary digraph D, it is clearly thatλ(D)≤δ(D), so we call D maximally edge-connected also known as λ-optimal when satisfying λ(D)=δ(D). A λ-cut is called trivial, if it consists of edges adjacent from orto a vertex of minimum degree. We call D super-edge-connected (for short super-λ)[5],if every minimum λ-cut is trivial. Then if D is super-λ, it must be λ-optimal.In order to more exactly describe the reliability of network, Fricke and so on[6]proposed the concept of local-edge-connectivity. The local-edge-connectivity of twovertices u and v in digraph D is denoted by λ(u, v)=min{|(X, Y)|: u∈X V (D)\{v}, Y=V (D)\X}. A minimum (X, Y) is called a λ(u, v)-cut of D. Clearly,λ(u, v)≤min{d+(u), d (v)}, so we call D maximally local-edge-connected[6], for shortmlec when λ(u, v)=min{d+(u), d (v)} for arbitrary vertices u and v.For the case that digraphs are maximally local-edge-connected, in order to moredeeply measure the reliability of network, Gao Jingzhen[7]proposed the concept of super-local-edge-connectivity. If for any vertices u and v of digraph D, every λ(u, v)-cut (X, Y)consists of edges adjacent from the vertex u, or adjacent to the vertex v, that is X={u}or Y={v}, then we call D super-local-edge-connected, for short slec.Obviously, when digraph D is super-local-edge-connected, it must be super-λ andmaximally local-edge-connected.In the second chapter, we mainly discuss sufcient conditions for graphs to be max-imally local-edge-connected, specifically including distance maximal set conditions andneighborhood conditions. Let (D)=min{+(D),(D)}, we have the following re-sults:Theorem2.1.4Let D be a strongly connected digraph, If forall3-distance maximal pairs of vertex sets S, T, there exists a vertex s∈S∪T with and satisfying thenD is maximally local-edge-connected.Theorem2.1.5Let D be a strongly connected digraph, If for all3-distance maximal pairs of vertex sets S, T, there exists an isolated edge st in D[S∪T]satisfying, then D is maximally local-edge-connected. Theorem2.2.3Let D be a digraph of order n with minimum degree for each vertex s with, then D is maximally local-edge-connected. Theconditions are best possible.In the third chapter, we mainly discuss the local-edge-connectivity of bipartite di-graphs.Firstly, we give a Fan-type condition for bipartite digraph to be maximally local-edge-connected, and give an example to explain that the condition is best possible.Theorem3.1.2Let D be a bipartite digraph of order n and minimum degreeor arbitrary pair of vertices x, y in the same part, thenD is maximally local-edge-connected.Then, we give neighborhood conditions for bipartite digraph to be maximally local-edge-connected and super-local-edge-connected, and give examples to show that theseconditions are best possible.Theorem3.2.3Let D be a bipartite digraph of order n and minimum degree δ,for each vertex s with then D is maximally local-edge-connected. Theorem3.2.7Let D be a bipartite digraph of order n and minimum degreefor each vertex s with then D is super-local-edge-connected.In the forth chapter, using the well-known Turan Theorem, we mainly present de-gree sequence conditions for maximally and super-local-edge-connected oriented graphsdepending on the clique number, and have the following results.Firstly we give some symbols. Let ν=1when the order n of oriented graphdiscussed is even, otherwise let ν=0. When the clique number≤p and the min-imum out-degree (in-degree, degree) of the oriented graph discussed is then D is maximally local-edge-connected.Theorem4.1.11Let D be an oriented graph of order n, clique number then D is maximally local-edge-connected.Theorem4.1.12Let D be an oriented graph of order n, clique number ω(D)≤p,with degree sequence, then D is maximally local-edge-connected.Theorem4.2.4Let D be an oriented graph of order n, clique number ω(D)≤p,with out-degree sequence The conditions of Theorem4.2.4,4.2.6are best possible. |
PDF Full Text Request