| Graph theory is an ancient but quite active subject, and is also a very practical subject. It is the important mathematical tools of studying the engineering technology, natural sciences and so on, the application is quite extensive. In modern society, the relationship between people’s daily life, study, work, and internet networks of multipro-cessor becomes increasingly close. The reliability and fault-tolerability of networks are widely concerned. Naturally, in recent years the research into the reliability and fault-tolerability topic of networks has become a hot research topic at home and abroad.When designing and analyzing the reliability and fault-tolerability of large-scale networks, an important model is to abstract the topological structure of the network into a (di-)graph D= (V, E). Then vertices of D express processors, and edges connected vertices represent direct communication between the processors (directed edge represents that there is only one-way link between the processors). 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 p∈(0,1). Then probability of D being not connected is given by The number of edges of D is denoted by m,λ(D) is the edge connectivity of D, and the number of edge cuts of size i is denoted by Ci(D). And the probability of D being connected R(G,p)= 1-P(G,p) can be used to measure the reliability of the network. Obviously the smaller P(D, p) is, the better the reliability of networks is. However, for a digraph, it is NP-hard to make sure all of the coefficient. Colbour made further explanations for that. There is a similar discussion assuming that all edges do not fail, and all vertices independently fail with equal probability p∈(0,1).Edge connectivity is a important parameters in reflecting the connectivity of (di-graphs. But to precisely describe the connectivity of graphs, classic edge connectivity has some obvious deficiencies:Firstly, even two (di-)graphs with the same edge con-nectivity may have different reliability. Secondly, we can not differentiate between the different types of (di-)graphs which result from removing A disconnecting edges. Lastly, 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, since 1983 Harary proposed the concept of conditional edge connectivity, after 30 years of development, the edge connectivity involved increasingly rich content and specific, including maximally edge connectivity, super edge connectivity, maximally local edge connectivity and super local edge connectivity, etc. At present, we have extensive and thorough research for this field. In this paper, we will continue to discuss the properties of edge connectivity of (di-) graphs on the basis of previous work.The first chapter mainly introduced the research background, some existing results, some basic concepts and terminology symbol involved in this paper.Firstly, the second chapter mainly present degree sequence conditions for super edge connected oriented graphs depending on the clique number.For brevity, let v= 1, when the order n of oriented graph discussed is even. Otherwise let v= 0; When the ω(D)≤p, and the minimum out-degree(in-degree, degree)of the oriented graph discussed is δ+,(δ-,δ), Let μ+= maxTheorem 2.1.5 Let D be a oriented graph of order n, clique number ω(D)≤ pand p≥ 4, with out-degree sequence d+1≥ d+2≥ ···≥ d+n(=δ+≥2), and in-degree sequence d-1≥d-2≥···≥d-n(=δ-≥2). If Then D is super-edge-connected.Theorem2.1.6 Let D be a oriented graph of order n, clique number ω(D)≤ p andp≥4, degree sequence d≥ ≥···≥dn(=δ≥ 2) ap/p-3), Then D is super-edge-connected.Theorem2.1.7 Let D be a oriented graph of order n, clique number ω(D)≤p and p≥4,degree sequence d1≥d2≥…≥dn(=δ≥2). Then D is super-edge-connected.Then we mainly present degree sequence conditions for maximally local-edge-connected and super local-edge-connected directed and oriented graphs depending on the clique number,The following results were obtained:Theorem 2.2.4 Let D be a oriented graph of order n,clique number ω(D)≤p, degree sequence d1≥ d2≥…≥ dn(=δ),△’=△’(D).If n≤4[p-1/pδ]-1 or if n≥4[p-1/pδ] and for some k,1≤k≤2δ+1,have Then D is maximally local-edge-connected.Theorem 2.3.4 Let D be a directed graph of order n,clique number ω(D)≤p, degree sequence d1≥d2≥…≥dn(=δ),△’=△’(D).If n≤2[p-1/pδ] or if n≥2[p-1/pδ] and for some k,1≤k≤[p-1/pδ],have Then D is maximally local-edge-connected.Theorem 2.3.11 Let D be a oriented graph of order n,clique number ω(D)≤p, degree sequence d1≥d2≥…≥dn(=δ≥3),△’=△’(D).If n≤2[p-q/pδ]—3 or if n≥2[p-1/pδ]—2 and for some k,1≤k≤[p-1/pδ]—1,have Then.D is super local-edge-connected.Firstly, the first chapter present degree sequence conditions for maximally local-edge-connected of directed graphs:Theorem 3.1.3 Let D be a directed graph of order n,degree sequence d1≥d2≥ ...≥dn(=δ),△’=△’(D).If δ≥[2/n] or if δ≤[2/n]—1 and for somek,1≤k≤δ+1,have Then D is maximally local-edge-connected.Then, we discuss degree sequence conditions for edge-connected of bipartite directed graphs:Theorem 3.2.3 Let D be a bipartite directed graph of order n, degree sequence d1≥d2≥···≥ dn(= δ). If δ≥ [n/4]+1 or if δ≤[n/4]and for somek,1≤k≤δ , have Then D is maximally edge-connected.Theorem 3.2.5 Let D be a bipartite oriented graph of order n, degree sequence d1≥d2≥···≥ dn(= δ)dn(= δ≥2)If δ≥[n+3/8] or if δ≤[n+2/8] and for somek.1≤k≤ 4δ-1, have Then D is super edge-connected.Theorem 3.2.7 (1) Let D be a bipartite oriented graph of order n, degree se-quence d1≥d2≥···≥ dn(=δ≥1),△’=△’(D).If δ≥[n+1/8] or if δ≤[n/8] and for somek,1≤k≤4δ, have Then D is maximally local-edge-connected.(2) Let D be a bipartite oriented graph of order n, degree sequence d1≥d2≥···≥ dn(=δ> 2), △’= △’(D). If δ≥[n+3/8] or if δ≤[n+2/8] and for somek,1≤k≤4δ-1, have Then D is super local-edge-connected. Last, we discuss inverse degree sequence conditions for maximally edge-connected and super edge-connected of oriented graphs.Theorem 4.1.4 Let D be a connected triangle-free oriented graph of order n, the minimum degree S, the edge connectivity A. If 5>[8/n]+1 or if δ≤[8/n] and Then D is maximally edge-connected.Theorem 4.2.3 Let D be a strongly connected triangle-free oriented graph of order n, the minimum degree S, the edge connectivity λ. If δ> [//n+3] or if δ≤[8/n+2] and Then D is super edge-connected. |
PDF Full Text Request