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.