Symmetry properties of resolving sets and metric bases in hypercubes |
| |
Authors: | Nebojša Nikolić Mirjana Čangalović Igor Grujičić |
| |
Affiliation: | 1.Department of Mathematics, Faculty of Organizational Sciences,University of Belgrade,Belgrade,Serbia |
| |
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 (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 (nge 19) better than the existing ones. Starting from these new bounds, some existing upper bounds for (23le nle 90) are improved by a dynamic programming procedure. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|