A187103 -id:A187103 - cp's OEIS frontend

A303735 a(n) is the metric dimension of the n-dimensional hypercube.

1, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 8

Offset: 1

Manuel E. Lladser, Apr 29 2018

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 11 terms coincide with A187103. - Omar E. Pol, Apr 29 2018 [updated by Pontus von Brömssen, Apr 06 2023]
Independent Verfication: Using the MaxSat solver RC2 (Ignatiev et al., 2019), and symmetry breaking constraints, I have verified the first 10 terms. In the previous references given, it is not clear which of the terms have been verified and which only have upper bounds verified. - Victor S. Miller, Mar 27 2023

			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.

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

Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva, RC2: an efficient MaxSAT solver, Journal on Satisfiability, Boolean Modelling and Computation 11 (2019), 53-64; alternative link.
Lucas Laird, Richard C. Tillquist, Stephen Becker, and Manuel E. Lladser, Resolvability of Hamming Graphs, arXiv:1907.05974 [cs.DM], 2019.
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).
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Metric Dimension

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).
Cf. A187103.

a(11) from Victor S. Miller, Apr 04 2023

a(12)-a(13) from Victor S. Miller, May 03 2023

A187102 Minimum number of function evaluations in each step of an explicit Runge-Kutta method of order n.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 9, 11

Offset: 1

Pontus von Brömssen, Mar 04 2011

a(n)>=n+3 for n>=8 (Butcher 1985).

J. C. Butcher, On the attainable Order of Runge-Kutta methods, Math. Comp. 19 (1965) 408-417.
J. C. Butcher, The non-existence of ten stage eighth order explicit Runge-Kutta methods, BIT 25 (1985) 521-540.
A. R. Curtis, An eighth order Runge-Kutta process with eleven function evaluations per step, Numer. Math. 16 (1970) 268-277.
MathOverflow, What is the minimum number of stages s required for a Runge-Kutta type numerical method of given order p?, 2019.
Wikipedia, Runge-Kutta methods.

Cf. A187103, A087803.

a(n) = min{k; A187103(k)=n}.

cp's OEIS Frontend

A303735 a(n) is the metric dimension of the n-dimensional hypercube.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions