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 $\mathit{\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 $\mathit{\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.