Hamiltonicity of hypercubes with a constraint of required and faulty edges |
| |
Authors: | Lih-Hsing Hsu Shu-Chung Liu Yeong-Nan Yeh |
| |
Affiliation: | (1) Department of Computer Science and Information Engineering, Providence University, Taichung County, Taiwan;(2) General Education Center, China University of Technology, Hsinchu, Taiwan;(3) Institute of Mathematics, Academia Sinica, Taipei, Taiwan |
| |
Abstract: | Let R and F be two disjoint edge sets in an n-dimensional hypercube Q n . We give two constructing methods to build a Hamiltonian cycle or path that includes all the edges of R but excludes all of F. Besides, considering every vertex of Q n incident to at most n−2 edges of F, we show that a Hamiltonian cycle exists if (A) |R|+2|F|≤2n−3 when |R|≥2, or (B) |R|+2|F|≤4n−9 when |R|≤1. Both bounds are tight. The analogous property for Hamiltonian paths is also given. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Lih-Hsing Hsu’s research project is partially supported by NSC 95-2221-E-233-002. Shu-Chung Liu’s research project is partially supported by NSC 90-2115-M-163-003 and 95-2115-M-163-002. Yeong-Nan Yeh’s research project is partially supported by NSC 95-2115-M-001-009. |
| |
Keywords: | Hamiltonian cycles and paths Edge-fault-tolerance Required edge Hypercubes |
本文献已被 SpringerLink 等数据库收录! |
|