Symmetry properties of resolving sets and metric bases in hypercubes

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 \(Q_n\), 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\ge 19\) better than the existing ones. Starting from these new bounds, some existing upper bounds for \(23\le n\le 90\) are improved by a dynamic programming procedure.