Groupe d’études et de recherche en analyse des décisions

# The Metric Dimension of Hypercubes

## Mirjana Cangalovic – University of Belgrade, Serbie

The hypercube $$Qn$$ of dimension n is the graph whose vertices are all $$n$$- dimensional binary vectors and where two vertices are adjacent if they differ only in one coordinate. Here we theoretically prove some symmetry properties of resolving sets in $$Qn$$ and illustrate how they can be used to reduce the complexity of a procedure for finding the so called metric dimension $$\beta (Qn)$$ of $$Qn$$, i.e. the minimal cardinality of a resolving set in $$Qn$$. Such a reduction is implemented within a simple constructive greedy heuristic which succeeded to find upper bounds of $$\beta (Qn)$$ for higher values of dimension $$n$$, for which the existing VNS and GA algorithms, developed for an arbitrary graph, failed.