A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges |
| |
Authors: | Wen-Qing Wang |
| |
Affiliation: | Department of Mathematics and Information Science, Zhangzhou Teachers College, Zhangzhou, Fujian 363000, China |
| |
Abstract: | In this paper, we consider the problem of a fault-free Hamiltonian cycle passing through prescribed edges in an n-dimensional hypercube Qn with some faulty edges. We obtain the following result: Let n?2, F⊂E(Qn), E0⊂E(Qn)\F with 1?|E0|?2n−3, |F|<n−(⌊|E0|/2⌋+1). If the subgraph induced by E0 is a linear forest (i.e., pairwise vertex-disjoint paths), then in the graph Qn−F all edges of E0 lie on a Hamiltonian cycle. |
| |
Keywords: | Hypercube Cycle Edge fault tolerance Hamiltonian cycle Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|