The Conditional Arc Connectivity Of Digraphs

One fundamental consideration in the design of large-scale networks is reliability(fault-tolerance),which can be measured by the edge connectivity of graphs.As an more accurate index,the restricted edge connectivity,a generalization of edge connectivity,was proposed and received much attention.As generalizations of restricted edge connectivity to digraphs,cycle arc connectivity ?c(D),strongly restricted arc connectivity ?2(D),restricted arc con-nectivity ?'(D)were introduced.In this paper,we introduce conditional arc connectivity as another generalization of restricted edge connectivity.Let D be a strong digraph.An arc subset S of D is a conditional arc cut of D if D-S is not strong and the minimum degree ?(D-S)?1.A strong digraph D is called?(1)-connected if it contains a conditional arc cut.The conditional arc connectivity of D,denoted by ?(1)(D),is the minimum cardinality over all conditional arc cuts of D.Kautz graph is the topological structure of Kautz network,which is regarded as one of competitive large scale networks.This thesis consists of four chapters,which introduce some properties of conditional arc connectivity and determine the conditional arc connectivity of Kautz digraphs.In Chapter 1,after giving the used basic concepts and notations,we give the research background,main notions and main results of this thesis.In Chapter 2,we first show that the conditional arc connectivity is a generalization of restricted edge connectivity,then discuss the relationship between conditional arc connec-tivity and strongly arc connectivity ?2(D),cycle arc connectivity ?c(D)and restricted are connectivity ?'(D).Next,we prove that,if a digraph D contains a strongly restricted arc cut,then ?2(D)??(1)(D)??c(D)??'(D).At last,we illustrate that the four generalizations of restricted edge connectivity are different.Volkmann has given an upper bound ?(D)on restricted arc connectivity ?'(D).In Chapter 3,we show that if the minimum degree of a digraph D is larger than its girth,then ?(1)(D)??(D),then illustrate that this result is best possible.As an application,we determine the conditional arc connectivity of Kautz digraphs.Super arc connectivity is a graph property closed to the reliability of networks.In Chapter 4,we introduce the notion of the arc fault tolerance S?(D)of a digraph D with respect to super arc connectivity.By the means of conditional arc connectivity,we give a characterization of super arc connectivity and then study the bounds on S?(D).As an application,we determine the arc fault tolerance of Kautz digraphs with respect to super arc connectivity.