

A303735


a(n) is the metric dimension of the ndimensional hypercube.


1




OFFSET

1,2


COMMENTS

The metric dimension of a graph is the least number of nodes needed to characterize uniquely any other vertex by its vector of distances to those nodes. Determining the metric dimension of a general graph is a known NPcomplete problem. It is not known, however, whether or not the metric dimension of hypercubes is NPcomplete.
The nondecreasing sequence a(n) provides the metric dimension of the ndimensional hypercube (i.e., with 2^n vertices) for 1 <= n <= 10, computed by brute force. Using an approximation algorithm, Mladenović et al. claim that the next seven terms in the sequence are 8, 8, 8, 9, 9, 10, 10.
Observation: first 10 terms coincide with A187103.  Omar E. Pol, Apr 29 2018


REFERENCES

Harary, F. and Melter, R. A. "On the metric dimension of a graph." Ars Combinatoria, 2:191195 (1976).


LINKS

Table of n, a(n) for n=1..10.
N. Mladenović, J. Kratica, V. KovačevićVujcic, and M. Čangalović, Variable neighborhood search for metric dimension and minimal doubly resolving set problems, European Journal of Operational Research, 220:328337 (2012).


EXAMPLE

The metric dimension of a complete graph on n vertices (denoted as K_n) is (n  1). For n = 1 the hypercube is isomorphic to K_2, so a(1)=1.
For n = 2, the hypercube has vertices (0,0), (0,1), (1,0), and (1,1), which form a simple cycle. Since each of these nodes has two other nodes at the same distance from it, a(2) >= 2. Using nodes (0,1) and (1,1) to encode all nodes by their distance to these two nodes, we find that (0,0) <> (1,2); (0,1) <> (0,1); (1,0) <> (2,1); and (1,1) <> (1,0). Since the vectors of distances (1,2), (0,1), (2,1), and (1,0) are all different, a(2) = 2.


CROSSREFS

Cf. A008949 (number of vertices on the hypercube graph Q_n whose distance from a reference vertex is <= k).
Cf. A066051 (number of automorphisms of hypercubes).
Sequence in context: A126974 A089058 A282717 * A187103 A080444 A082288
Adjacent sequences: A303732 A303733 A303734 * A303736 A303737 A303738


KEYWORD

nonn,hard,more


AUTHOR

Manuel E. Lladser, Apr 29 2018


STATUS

approved



