Higher Order Connectedness Of A Graph

With the rapid development of information networks, performance of the network come into focus, that is, information is relayed through intermediate nodes before reaching its destination. A network can be modeled as a digraph, in which vertices correspond to the processors and arcs correspond to the links. In particular, if all the links are bi-directional, then the digraph is a graph. The diameter of the graph or the digraph is an important factor measuring the performance of the network since it determines the maximum communication delay between any pair of processors. In this background, small diameter is preferred. The knowledge about graph theory is applied to solve the relation of transformation delay and diameter of graph. Some diameter vulnerability is obtained through the analysis and argument of some digraph.In this paper, we study the diameter vulnerability of the directed cycle Cm and the directed torus Tm,n with respect to arc addition or deletion, that is, D-0(G) is the maximum number of arcs the addition of which dose not change the diameter of G; D+k(G) is the minimum number of arcs the deletion of which increases the diameter of G by at least k. We give a formula for D-0(G) if G is vertex transitive and every vertex has a unique vertex which is farthest from it. As consequences, the values of D-0for the directed cycle and the directed torus can be determined. The values of D+k for these two digraphs are also determined.This thesis is divided into four chapters. In Chapter1, we introduce the background of our study. Then we state the main results in this thesis. In Chapter2, we study the diameter vulnerability of the directed cycle Cm and the directed torus Tm,n with respect to arc addition.1. For m≥4, D*(Cm)=[(3m)/4]-1, where D*(Cm) the minimum diameter among those digraphs obtained from Cm by the addition of exactly two arcs.2. For m>4, D-k(Cm)=2holds for any integer k with1≤k≤[m/4].3. For max{m,n}≥4, D-(Tm,n)=2.4. Suppose m≥A(4+k-1). Then D-k(Tm,n)=2.5. Suppose m≥4k and k≤[n/2]. Then D-k(Tm,n)≤4.In Chapter3, we obtain three conclusion which dose not change the diameter of the directed cycle Cm and the directed torus Tm,n with respect to arc addition. As follows 1.For any strongly connected digraph G=(V,A) on n vertices and m arcs which has no digon,Dr-0(G)=n(n-1)/2-m,where Dr-0(G)is the maximum number of arcs that can be added to G such that the diameter remains to be the same and there is no digon in the resulting digraph.2.Let G be a vertex transitive digraph on n vettices and m arcs, u be an arbitrary vertex in V(G).For r=0,1,...,D(G),suppose|Nr(u)|=nr,and nD(G)=1.Then3.D-0(Cn)=(n-2)(n+1)/2.4.Suppose s≤t.Then D-0(Ts,t)=3/2s2t2+8st+66-40s-33t+6s2+s3-3/2s2t.In Chapter4,we show that the minimum number of arcs the deletion of which increases the diameter of the directed cycle Cm and the directed torus Tm,n by at least k.As follows1.D+k(G)≤δ(G)holds for any strongly connected digraph G on at least two vertices and any positive integer k,where δ(G)=min{dG+(u),dG-(u)|u∈V(G)}.2.D+k(Cn)=1for any k≥1.D+1(Ts,t)=1,and D+k(Ts,t)=2for any k≥2.