# Resolvability of Hamming Graphs

arXiv: https://arxiv.org/abs/1907.05974 · HTML: https://mlsanity.com/paper/1907.05974/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2019.

## Built on by (most cited first, 1 of 1)

- [Metric Dimension and Resolvability of Jaccard Spaces](https://mlsanity.com/paper/2405.11424/) (2024)

## Abstract (arXiv)

A subset of vertices in a graph is called resolving when the geodesic distances to those vertices uniquely distinguish every vertex in the graph. Here, we characterize the resolvability of Hamming graphs in terms of a constrained linear system and deduce a novel but straightforward characterization of resolvability for hypercubes. We propose an integer linear programming method to assess resolvability rapidly, and provide a more costly but definite method based on Gr"obner bases to determine whether or not a set of vertices resolves an arbitrary Hamming graph. As proof of concept, we identify a resolving set of size 77 in the metric space of all octapeptides (i.e., proteins composed of eight amino acids) with respect to the Hamming distance; in particular, any octamer may be readily represented as a 77-dimensional real-vector. Representing k-mers as low-dimensional numerical vectors may enable new applications of machine learning algorithms to symbolic sequences.