The Fault-tolerant Hamiltonicity Of Some Kinds Of Networks

In general,the multiprocessing system is regard as the network,where the pro-cessor of the multiprocessing system corresponds to the vertex of the network,and the connection between processors corresponds to the edge of the network.Since faults are inevitable when the large scale multiprocessing system is in operation,the system should be fault-tolerant.The fault-tolerance of system corresponds to the fault-tolerance of the network.The Hamiltonicity is one of the most basic requirements for designing networks.It leads to this article focusing on the edge-fault-tolerant Hamiltonicity,that is,whether there is a fault-free Hamiltonian cycle in the network with faulty edges.Be-cause the network containing a fault-free Hamiltonian cycle requires that each vertex is incident with at least two fault-free edges,so it is meaningful to consider the conditional edge-fault-tolerant Hamiltonicity.Combining mathematical induction and classified discussion about the random dis-tribution of faulty edges,this paper studies the Hamiltonicity of the compound network DVcube and the edge-fault-tolerant Hamiltonicity of the compound network DHcube,and gives the conditional edge-fault-tolerant Hamiltonicity of the k-dimensional data center network with n-port switches Dk,n.This thesis is organized as follows.Chapter 1 is the introduction.We introduce basic definitions and preliminaries related to this thesis and give the background of the(conditional)edge-fault-tolerant Hamiltonicity,the definitions of networks we studied and the main work of this thesis.In Chapter 2,we give related properties of the compound network DVcube and prove that every network in DVcube DV(m,d,n)is Hamiltonian.As corollaries of the result,some known results gotten by Hung in[Theoret.Comput.Sci.498(2013)28-45]can be obtained directly.Moreover,we study the edge-fault-tolerant Hamiltonicity of the compound network DHcube and show that every network in DHcube DH(m,d,n)is(n-1)-edge-fault-tolerant Hamiltonian for any n?2.In Chapter 3,based on related properties of the data center network Dk,n,we study the conditional edge-fault-tolerant Hamiltonicity of Dk,n and prove that Dk,n is condi-tional(2n + 2k-9)-edge-fault-tolerant Hamiltonian for any k ? 0 and n ? 2,except k = 1 and n ? 6.Our result improves the known result that Dk,n is(n + k-3)-edge-fault-tolerant Hamiltonian in the sense of the number of faulty edges.In Chapter 4,we summary the thesis and give further research directions.