|
%I #62 May 03 2023 17:09:18
%S 1,2,3,4,4,5,6,6,7,7,8,8,8
%N a(n) is the metric dimension of the n-dimensional hypercube.
%C 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.
%C 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.
%C Observation: first 11 terms coincide with A187103. - _Omar E. Pol_, Apr 29 2018 [updated by _Pontus von Brömssen_, Apr 06 2023]
%C Independent Verfication: Using the MaxSat solver RC2 (Ignatiev et al., 2018), 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
%D Harary, F. and Melter, R. A. "On the metric dimension of a graph." Ars Combinatoria, 2:191-195 (1976).
%H Alexey Ignatiev et al., <a href="https://alexeyignatiev.github.io/assets/pdf/imms-jsat19-preprint.pdf">RC2: an Efficient MaxSAT Solver</a>, Journal on Satisfiability, Boolean Modeling, and Computation, (2018).
%H Lucas Laird, Richard C. Tillquist, Stephen Becker, and Manuel E. Lladser, <a href="https://arxiv.org/abs/1907.05974">Resolvability of Hamming Graphs</a>, arXiv:1907.05974 [cs.DM], 2019.
%H N. Mladenović, J. Kratica, V. Kovačević-Vujcic, and M. Čangalović, <a href="https://doi.org/10.1016/j.ejor.2012.02.019">Variable neighborhood search for metric dimension and minimal doubly resolving set problems</a>, European Journal of Operational Research, 220:328-337 (2012).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MetricDimension.html">Metric Dimension</a>
%e 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.
%e 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.
%Y Cf. A008949 (number of vertices on the hypercube graph Q_n whose distance from a reference vertex is <= k).
%Y Cf. A066051 (number of automorphisms of hypercubes).
%K nonn,hard,more
%O 1,2
%A _Manuel E. Lladser_, Apr 29 2018
%E a(11) from _Victor S. Miller_, Apr 04 2023
%E a(12)-a(13) from _Victor S. Miller_, May 03 2023
|
