Landmarks in Binary Tree Derived Architectures.

Abstract

Let M = {v1, v2 ... vl} be an ordered set of vertices in a graph G. Then (d(u, v1), d(u, v2) ... d(u, vl)) is called the M-location of a vertex u of G. The set M is called a locating set if the vertices of G have distinct M-locations. A minimum locating set is a set M with minimum cardinality. The cardinality of a minimum locating set of G is called Location Number L(G). This concept has wide applications in motion planning and in the field of robotics. In this paper we consider networks with binary tree as an underlying structure and determine minimum locating set of such architectures.We show that the location number of an n-level X-tree lies between 2 −3 and 2 −3 + 2. We further prove that the location number of an n × n mesh of trees is greater than or equal to n/2 and less than or equal to n.