Research On The Cycle Embedding Of The Hypercubes With Faulty Edges

It is well known that the hypercube is one of the most popular interconnection networks. It possesses many excellent properties which bring it's widely application in the parallel system. The research on hypercubes dates back to long ago. Rings and linear arrays are two fundamental networks for parallel and distributed computation. Many efficient algorithms with low communication cost were originally designed based on them. If one network contains Hamiltonian cycles (Hamiltonian paths) and cycles of variable lengths, then it can effectively simulate the algorithms designed based on rings and linear arrays. Thus, it is meaningful to study the cycle embedding problems. Failures are inevitable when a large computer system is put in use. Therefor, the fault-tolerant capacity of a networks is a critical issue in parallel computing. Hence, it is important to study cycle embedding of the faulty hypercubes. In this thesis, our main results are as follows.(1) We obtained a sufficient condition for the existence of fault-free hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges. This result generalizes Dvorak's work on the existence of Hamiltonian cycle passing through prescribed edges in a health hypercube.(2) W proved the existence of fault-free cycle with every even length from 2^h-1(n+1-h) + 2(h -1) to 2ⁿ passing through prescribed h edges in a hypercube with f faulty edges. This result improves the number of faulty edges of Chen's work [7] from f