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 '19 at 23:02
  • $\begingroup$ Is choosing a random set with appropriate size considered as "explict"? $\endgroup$ – LeechLattice May 26 '19 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$ – Stefan Mesken May 26 '19 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$ – Stefan Mesken May 26 '19 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.