Conditional edge-fault Hamiltonicity of augmented cubes |
| |
Authors: | Sun-Yuan Hsieh Yi-Ru Cian |
| |
Affiliation: | Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 70101, Taiwan |
| |
Abstract: | The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n?3) with faulty edges up to 4n-8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated. |
| |
Keywords: | Augmented cubes Fault-tolerant embedding Graph-theoretic interconnection networks Hamiltonian cycles Hamiltonicity |
本文献已被 ScienceDirect 等数据库收录! |
|