Hypercube metric dimension
Computational experiments and machine-checkable certificates for hypercube metric dimension.
Identifying vertices by their distances
The metric dimension of a graph asks how many reference vertices are needed to uniquely identify every vertex from its distances to those references. For a hypercube, graph distance is Hamming distance between binary strings.
My manuscript, Exact Metric Dimensions and Improved Upper Bounds for Hypercubes, presents resolving-set constructions and computational search methods. The accompanying repository contains certificates, verification code, and reproduction instructions.
The OEIS connection
OEIS A303735 records the metric dimension of each hypercube: how many reference vertices distinguish all its vertices by distance. Its Extensions section credits me with the terms for dimensions 14 and 15, both equal to 9, on September 1, 2026. The entry links to this project’s certificates, verifiers, and manuscript.
The sequence predates my contribution. My work extends it with these two terms and supplies computational evidence that readers can inspect and reproduce.