| dc.description.abstract | The architecture of an interconnection network is usually represented by a graph. There exist mutually conflicting requirements in designing and topology of interco- nnection networks. It became almost impossible for us to design a network which is optimum in all aspects. The hypercube network is one of the most popular topologies among the interconnection networks. It has widely used due to many of its attractive properties, including regular, symmetric, strong connectivity and relative small diameter [48, 64] etc. The first paper dealing directly with hamiltonian property and fault- tolerant property appeared in 1976 Hayes [38]. Since that time the interest in hamiltonian property and fault-tolerant property has been on increase. Many combinatorial, algebraic, and other mathematical structures are linked to hamiltonian property and fault-tolerant property. There are lots of intriguing problems and significant results. Excellent surveys of them are provided by Hayes [38], Simmons [66], Lewinter and Widulski [46] etc.
There are various fault-tolerant hamiltonian problems, such as cycle (path) embedding problems in hamiltonian faulty interconnection networks. However, any bipartite graph G is not hamiltonian connected for V(G).
Any hamiltonian bipartite graph G = (V0; V1;E) satisfies |V0| = |V1|. Simmons [66] introduced the concept of hamiltonian laceability for hamiltonian bipartite graph. Hsieh et al. [41] introduced the concept of strongly hamiltonian laceability. Lewinter and Widulski [46] further introduced the concept of hyper-hamiltonian laceability. The Hamiltonian laceability, which deals with embedding a hamiltonian path in a given bipartite graph, is an important topic in interconnection networks. The cycle (path) embedding problem is a derivation of hamiltonian problems.
In this thesis, there are four chapters in this thesis. We’’ll study the path and cycle embedding in faulty hypercubes. In Chapter 1, we mention some basic definitions and classical results on hamiltonian problem. In Chapter 2, we discuss hamiltonian problems on some faulty hypercubes. In Chapter 3, we discuss the cycle and path embeddingproblem, which deals with all the possible lengths of cycle and path in faulty hypercubes under some conditions. In Chapter 4, we propose and discuss related problems: Mutually independent hamiltonian paths and cycles problems in hypercubes. In the final section, we give our concluding remarks. | en_US |