Generalized honeycomb torus is Hamiltonian |
| |
Authors: | Xiaofan Yang David J Evans Graham M Megson |
| |
Affiliation: | a College of Computer Science, Chongqing University, Chongqing, 400044, PR China b School of Computing and Mathematics, Nottingham Trent University, Room N421a, Newton Building, Burton Street, Nottingham, NG1 4BU, UK c Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, USA d Department of Computer Science, School of Systems Engineering, University of Reading, PO Box 225, Whiteknights, Reading, Berkshire, RG6 6AY, UK |
| |
Abstract: | Generalized honeycomb torus is a candidate for interconnection network architectures, which includes honeycomb torus, honeycomb rectangular torus, and honeycomb parallelogramic torus as special cases. Existence of Hamiltonian cycle is a basic requirement for interconnection networks since it helps map a “token ring” parallel algorithm onto the associated network in an efficient way. Cho and Hsu Inform. Process. Lett. 86 (4) (2003) 185-190] speculated that every generalized honeycomb torus is Hamiltonian. In this paper, we have proved this conjecture. |
| |
Keywords: | Interconnection networks Generalized honeycomb torus Hamiltonian cycle |
本文献已被 ScienceDirect 等数据库收录! |
|