Hamiltonian properties of honeycomb meshes

Meshes are widely used topologies for Networks on Chip (NoC). Honeycomb meshes have better topological properties than Meshes. In order to communicate efficiently in a linear or cyclic manner, it is benefited that there is a Hamiltonian path or Hamiltonian cycle in NoC. In this paper, we give a necessary and sufficient condition for the existence of Hamiltonian path between any pair of vertices in a honeycomb mesh and for the existence of Hamiltonian path in a honeycomb mesh with one faulty vertex. Besides, we give a systematic method to construct a Hamiltonian path in Honeycomb meshes. © 2013 Elsevier Inc. All rights reserved.