Connectivity And Diagnosability Of Some Networks

A topological structure of an interconnection network can be modeled by a graph,it has been widely used by computer and engineering technicians.In this thesis,the terms "graph" and "interconnection network" are used interchangeably.Connectivity is used to determine the reliability and fault tolerance of a network.Extra connectiv-ity is a generalization of the classical connectivity and provides a more accurate tool for the reliability and the tolerance of networks.Hamiltonicity is one of the most basic requirements when designing a network.Designing multiprocessor systems without de?fects is nearly impossible,considering Hamiltonian path or cycle embedding in graphs with faulty elements is meaningful.Diagnosability is an important metric parameter for measuring the fault tolerance of a network.This thesis investigates the extra connectivity of graphs,fault-tolerance hamiltonic-ity and fault diagnosis of graphs.This thesis is organized as follows.Chapter 1 is an introduction part.We gave a brief introduction on the background of conditional connectivity of graphs,fault-tolerance hamiltonicity and fault diagnosis of networks.In Chapter 2,we introduce some basic definitions and preliminaries of graph theory related to this thesis.In Chapter 3,we study the extra connectivity of k-ary n-cubes Qnk.If n ? 3,we obtained the 3-extra connectivity of 3-ary n-cubes Qn3 is 8n-12.If n ? 3 and k ? 4,we obtained the 3-extra connectivity of k-ary n-cubes Qnk is 8n-9,the result is independent of the value of k.These results generalized the results about the 2-extra connectivity of Qn3 obtained by Zhao et al.and Qnk obtained by Hsieh et al.In Chapter 4,we study the fault-tolerance hamiltonicity of balanced hypercubes.Almost all results about fault-tolerance in BHn with only faulty vertices or only faulty edges.We consider the fault-tolerance of networks with both faulty vertices and edges.We first prove the existence of a Hamiltonian cycle in the balanced hypercube if it has both faulty vertices and edges not more than 2n-2 and faulty vertices not more than n-1.Let Fv and Fe be the set of faulty vertices and faulty edges,respectively,with |Fv| ?n-1 and |Fv| + |Fe| ? 2n-2 in BHn,where n ? 2.Then there exists a fault-free cycle of length 22n-2|Fv| in BHn.Then we prove that the balanced hypercube has the strong Hamiltonian laceability even if at most n-1 edges are faulty.Let x and y be two distinct vertices in the same partite set of BHn and Fe be the set of faulty edges with |Fe|?n-1,where n ? 1.Then,there is a fault-free x-y path in BHn whose length is 22n-2.In Chapter 5,we study the diagnosability of networks,including the pessimistic diagnosability,the conditional diagnosability and the g-good-neighbor diagnosability.Firstly,we study the pessimistic diagnosability under the PMC model.We first ob-tained the pessimistic diagnosability of some general k-regular and k-connected graphs Gn under some possible conditions.As applications,every pessimistic diagnosabil-ity of many famous networks including some known results,such as the alternating group graphs AGn,the alternating group networks ANn,the k-ary n-cubes Qnk,the star graphs Sn,and the matching composition networks MCN is obtained.These graphs have the same property:the maximum number of common neighbors between any two adjacent vertices are less than two.Then we study the pessimistic diagnosability of some networks without restriction the number of common neighbors between any two vertices,including the(n,k)-arrangement graphs An,k,(n,k)-star graphs Sn,k,balanced hypercubes BHn,bubble-sort star graphs BSn,augmented k-ary n-cubesA Qn,k,and data center networks DCell Dk,n etc.Secondly,we study the conditional diagnosability of the data center networks DCell Dk,n.After removing at most n+ 4k-5 faulty vertices in Dk,n,we analysis the remaining components of Dk,n.Using this,we show that the conditional diagnos-ability of the date center network Dk,n is n + 3k-3 for k ? 2 and n ?2 under the MM model and n+4k-3 for k? 2 and n? 4 under the PMC model.Lastly,we focus on the g-good-neighbor diagnosability.Let t,(G)and tg(G)be the conditional diagnosability and g-good-neighbor diagnosability,respectively,of a graph G.There are some different values of conditional diagnosability and 1-good-neighbor diagnosability for some kinds of graphs.We mainly consider the balanced hypercube BHn.We obtained the 1,2-good-neighbor diagnosability of BHn and prove that the 1-good-neighbor diagnosability is equal to its conditional diagnosability.In Chapter 6,we discuss some problems to be further studied.