Study On Fault Tolerance Of Graphs And Hypergraphs

As networks of massive-scales for multiprocessor computet systems are bound to gain more popularity in many fields,many theoretical problems have drawn considerable atten-tion,one of which is the fault tolerance of the network.The fault tolerance of networks refers to the ability of networks to remain connected or maintain certain properties in the presence of failures.The network is often modeled as a(di)graph,or even a hypergraph,and so,some fault-tolerant parameters of(di)graphs or hypergraphs can be used to evaluate the performance of the networks.Since symmetric networks possess many desirable properties,the fault tolerance of symmetric graphs is also an important consideration.The dissertation mainly focus on some fault-tolerant parameters for(di)graphs or hypergraphs about edge connectivity.There are four chapters in this dissertation,which are organized as blewIn the first chapter,firstly,the background and a brief introduction to the contents are given;secondly,we introduce the used basic notations and terminologies;finally,we intro-duce the fault-tolerant parameters and research advance of the related worksHypergraphs are the bridges connecting Graph theory,Combinatorial mathematics and Computer science,and the investigation on properties of hypergraphs is full of theoretical significance and application value.In the second chapter,we study the sufficient conditions for hypergraphs to be optimal edge connected or super edge connected.Particular,we con-firm sufficient conditions in terms of distance conditions,diameter(and girth)conditions,cardinality of order that ensure linear uniform hypergraphs to be optimal edge connected;and present sufficient conditions for uniform hypergraphs to be optimal edge connected in terms of cardinality of size,degree conditions and drgree sequence conditions.Besides,we also show sufficient conditions for uniform hypergraphs to be super edge connected in terms of cardinality of size and drgree sequence conditions.These generalize the corresponding well-known results for graphsThe property of connecting must be influenced when network faults occure,to measure how vulnerable for edge(arc)the(di)graph is with respect to optimal edge(arc)connectivity,in the third chapter,we investigate the edge(arc)fault tolerance of a(di)graph with respect to optimal edge(arc)connectivity.By measuring the relationship between the edge(arc)con-nectivity and minimum degree for the remaining(di)graph,which is obtained by removing some edge(arc)subset from the optimal edge(arc)connected(di)graph,we give the bounds or values on this edge(or arc)fault toletance under some conditions,and determine the exact value on this parameter for vertex transitive graph,edge transitive graph,de Bruijn digraph and a kind of Cartesian product digraph.The investigation on higher order edge connectivity for symmetric graphs comes into much focus,by argumenting the non-intersecting for ?(r)-atoms or ?(r)-superatoms,in the last chapter,we focus on the higher order edge connectivity of double-orbit graphs.At first,we characterize the super restricted edge connected double-orbit graphs H with two orbits of the same size and g(H)?5.Next,we determine when the half-vertex transitive graphs are 3-restricted optimal edge connected.At last,we completely characterize super 3-restricted edge connected half-vertex transitive graphs.