login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A303735 a(n) is the metric dimension of the n-dimensional hypercube. 1
1, 2, 3, 4, 4, 5, 6, 6, 7, 7 (list; graph; refs; listen; history; text; internal format)
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 NP-complete problem. It is not known, however, whether or not the metric dimension of hypercubes is NP-complete.

The nondecreasing sequence a(n) provides the metric dimension of the n-dimensional 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:191-195 (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:328-337 (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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 18 00:56 EDT 2019. Contains 326059 sequences. (Running on oeis4.)