Landmarks in Binary Tree Derived Architectures

Abstract

Let \(M = \{v_1, v_2, \ldots, v_t\}\) be an ordered set of vertices in a graph \(G\). Then \((d(u, v_1), d(u, v_2), \ldots, d(u, v_\ell))\) 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 the 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 a binary tree as an underlying structure and determine the minimum locating set of such architectures. We show that the location number of an \(n\)-level \(X\)-tree lies between \(2^{n-3}\) and \(2^{n – 3} + 2\). We further prove that the location number of an \(N \times N\) mesh of trees is greater than or equal to \(N/2\) and less than or equal to \(N\).