Honeycomb rectangular disks

Abstract

In this paper, we propose a variation of honeycomb meshes. A honeycomb rectangular disk HReD(m,n) is obtained from the honeycomb rectangular mesh HReM(m,n) by adding a boundary cycle. A honeycomb rectangular disk HReD(m,n) is a 3-regular planar graph. It is obvious that the honeycomb rectangular mesh HReM(m,n) is a subgraph of HReD(m,n). We also prove that HReD(m,n) is hamiltonian. Moreover, HReD(m,n) -f remains hamiltonian for any f is an element of V(HReD(m, n)) boolean OR E(HReD(m, n)) if n >= 6. (c) 2005 Elsevier B.V. All rights reserved.