Abstract

Meshes are widely used topologies for Network on chip (NoC). Honeycomb meshes have better topological properties than meshes. In this paper we have proposed a new planar architecture called 3D-Honeycomb Cage networks derived from, 3D-Honeycomb meshes. In order to communicate efficiently in a linear or cyclic manner, it is useful that there is a Hamiltonian path or Hamiltonian cycle in NoC. In this paper we have studied topological properties, specially discussed Hamiltonian properties in Honeycomb network after adding a new edge in the nth layer without any new edge crossings. Also we have proved an n dimensional 3D-Honeycomb Cage networks with two layers is Hamiltonian using Barnette conjecture which was recently proved by I.Cahit. A metric basis is a minimum set W of vertices of a graph G(V, E) such that for every pair of vertices u and v in V \ W, there exists a vertex w in W with the condition that the distance between u and w is not equal to v and w. The cardinality of W is called the metric dimension dim(G) of the graph G. Equivalently, for an ordered set M={m1,m2,m3,…,mp} of vertices in a connected graph G and a vertex u of G, the code( p-dimensional vector of distance coordinate) of u with respect to M is the p-vector CM (u) = (d(v, m1), d(v, m2), d(v, m3),…,d(v, mp)). The set M is called a resolving set for G if d(x, m) ≠ d(y, m) for x, y in V \ M and m in M. A resolving set containing a minimum number of vertices is called a minimum resolving set or a metric basis for G. In this paper, we have investigated the metric dimension of n dimensional 3D-Honeycomb Cage network with two layers, and found an upper bound for the metric dimension of n dimensional 3D- Honeycomb Cage Network with three layers. Finding a Hamiltonian cycle and a metric basis for an arbitrary graph are NP hard problems.