Fault-tolerant hamiltonian laceability of hypercubes |
| |
| Authors: | Chang-Hsiung TsaiJimmy J.M. Tan Tyne LiangLih-Hsing Hsu |
| |
| Affiliation: | Department of Computer and Information Science, National Chiao Tung University, Hsinchu, 30050 Taiwan, ROC |
| |
| Abstract: | It is known that every hypercube Qn is a bipartite graph. Assume that n?2 and F is a subset of edges with |F|?n−2. We prove that there exists a hamiltonian path in Qn−F between any two vertices of different partite sets. Moreover, there exists a path of length 2n−2 between any two vertices of the same partite set. Assume that n?3 and F is a subset of edges with |F|?n−3. We prove that there exists a hamiltonian path in Qn−{v}−F between any two vertices in the partite set without v. Furthermore, all bounds are tight. |
| |
| Keywords: | Hamiltonian laceable Hypercube Fault tolerance |
| 本文献已被 ScienceDirect 等数据库收录！ |
