The Study On Fault-tolerant Properties Of Enhanced Hypercube

With the expanding of parallel interconnection networks, processor faults and linkfaults may happen inevitably. In this case, the network must have some fault-tolerantproperties. The fault-tolerance of a network is that the network still can work when theresome number of processors and （or） links fault. It is more and more important to considerfault-tolerance of networks. Fault cycles, fault diameter, fault Hamiltonian are all importantparameters to measure the fault-tolerance of a network. In this paper, we investgate theedge fault-tolerant and vertex fault-tolerant properties of enhanced hypercube, and discussthe fault-tolerant cycles and paths embedding problems.This thesis mainly consists of four chapters, discussing some fault-tolerant propertiesof enhanced hypercube: conditional and standard fault-tolerant properties; vertexfault-tolerant properties and hyper Hamiltonian laceability.In the first chapter, we mainly give graph-theoretical terminology and notation. Wealso introduce the notations of some famous interconnection networks and panconnectivity,Hamiltoniancity, faulty-Hamiltoniancity, fault-tolerant pacyclicity, strongly Hamiltonianlaceability, restricted connectivity and so on. Then we list some known results on them.In the second chapter, we focus on the conditional fault-tolerant properties and hyperHamiltonian-laceability problem ofQ_n,k, and obtain the following two conclusions:（1）We showed the conditional edge-fault-tolerant pancyclicity of enhanced hypercube,and proof that ifQ_n,k（n≥3）has at least （2ⁿ3）faulty edges, where each vertex isincident with at least two fault-free edges, and n and k have the same（different） parity,then there exists a fault-free cycle of every even length from4to2ⁿ（there exist a fault-freecycle of every even length from4to2ⁿand a fault-free cycle of every odd length fromn-k+2to2ⁿ-1）.（2）We proofed the hyper Hamiltonian-laceability of enhanced hypercubeQ_n,k: Theenhanced hypercubeQ_n,k（1≤k≤n-1）is （n-2）edge fault tolerant hyperHamiltonian-laceability when n （≥3）and k （1≤k≤n-1）have the same parity.In the third chapter, we investgate the vertex-fault-tolerant properties ofQ_n,kand thelongest fault-tolerant paths embedding onQ_n,k. We obtain the following conclusions:（1）Two-vertices fault-tolerant pancycles embedding onQ_n,kand （n-2）vertex-fault-tolerant longest cycles embedding onQ_n,k.（2）Vertex and edge fault-tolerant longest paths and cycles embedding onQ_n,k.In the fifth chapter, we give conclusions of the full article and problems to be further studied.