Symmetry properties of resolving sets and metric bases in hypercubes

Abstract

In this paper we consider some special characteristics of distances between vertices in the n-dimensional hypercube graph Q(n) and, as a consequence, the corresponding symmetry properties of its resolving sets. It is illustrated how these properties can be implemented within a simple greedy heuristic in order to find efficiently an upper bound of the so called metric dimension beta(Q(n)) of , i.e. the minimal cardinality of a resolving set in Q(n). This heuristic was applied to generate upper bounds of beta(Q(n)) for n up to 22, which are for n >= 19 better than the existing ones. Starting from these new bounds, some existing upper bounds for 23 LT = n LT = 90 are improved by a dynamic programming procedure.