Definition. Let $G = (V;E)$ be a finite, undirected graph. $R = \{r_1, \ldots, r_k \} \subseteq V$. $R$ resolves $G$ if $$ V \to [0, \infty]^k, v \mapsto (d_G(v,r_1), \ldots, d_G(v, r_k)) $$ is injective (where $d_G$ is the graph metric associated to $G$).

The metric dimension of $G$ is the cardinality of the smallest resolving $R \subseteq V$.

Definition. Let $d,q \in \mathbb N$. The Hamming graph $H(d,q)$ is the graph with vertex set $\{1, \ldots, q\}^d$ in which two vertices $u = (u_1, \ldots, u_d), v = (v_1, \ldots, v_d)$ are adjacent iff they differ in a single spot, i.e. $| \{ i \mid v_i \neq u_i \} | = 1$.

It is known that the metric dimension of $H(d,q)$ is $\frac{(2 + o(1)) \cdot d}{\log_q(d)}$ (1).

I'm interested in explicit (2) resolving sets for Hamming graphs in the region of $d \sim 1000$ that come reasonably close (3) to their dimension metrics.

Unfortunately, since this lies outside of my area of expertise and I wasn't able to come up with an answer in the literature, I don't know whether this is even remotely possible.

(1) Since I'm unfamiliar with some of the notation in the published literature, I'm not 100% sure about this.

(2) as in computable with current day technology -- ideally already known and publicly available

(3) i.e. significantly smaller than $d$ as $\{ (\delta_{i,j})_{i = 1, \ldots, d} \mid j = 1, \ldots, d \}$ is a trivial resolving set of size $d$

  • $\begingroup$ Please give a link to a paper from the literature in the CS setting. Also why does the range of $V$ include $\infty$? $\endgroup$
    – kodlu
    May 25, 2019 at 23:02
  • $\begingroup$ Is choosing a random set with appropriate size considered as "explict"? $\endgroup$ May 26, 2019 at 4:47
  • $\begingroup$ @Bullet51 Any resolving set of small size that you can make available to me (so that I can actually use it in an algorithm) counts as 'explicit'. $\endgroup$ May 26, 2019 at 9:24
  • 1
    $\begingroup$ @kodlu $\infty$ is included since the graph may not be connected. And one relevant paper is chapter 6 of ON THE METRIC DIMENSION OFCARTESIAN PRODUCTS OF GRAPHS. $\endgroup$ May 26, 2019 at 9:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.