Weak $k$-metric dimension formula for Hamming graphs $K_n\square K_m$

The weak metric dimension of rectangular Hamming graphs

Let $n\ge3$, $m\ge n+1$, and $3\le k\le2n$ be integers. Then

$$\begin{aligned} &\operatorname{wdim}_k(K_n\square K_m)\\ &\quad=\begin{cases} m\lceil k/2\rceil,&k\text{ even},\\ m\lceil k/2\rceil-1,&k\text{ odd}. \end{cases} \end{aligned}$$

This proves Conjecture 6.1 of Fernández, Klavžar, Kuziak, Muñoz-Márquez and Yero, On the weak $k$-metric dimension of Hamming graphs. The layer-count identities used below are those of their Proposition 4.2; their Proposition 4.1 also shows that aligned pairs suffice when $k\ge4$. We give the identities explicitly and construct a set attaining the required lower bound, including when $k=3$.

1. Distances and layer counts

Write the vertices of $G=K_n\square K_m$ as $(i,j)$, where $0\le i<n$ and $0\le j<m$. The distance between two vertices is the number of coordinates in which they differ. For a subset $S\subseteq V(G)$, put

$$\begin{aligned} a_{ij}&=\mathbf1_{\{(i,j)\in S\}},\\ r_i&=\sum_{j=0}^{m-1}a_{ij},\\ c_j&=\sum_{i=0}^{n-1}a_{ij}. \end{aligned}$$

For distinct vertices $u,v$, define

$$\Delta_S(u,v)=\sum_{w\in S}|d(u,w)-d(v,w)|.$$

By definition, $S$ is weak $k$-resolving exactly when every such sum is at least $k$.

If $j\ne\ell$, then

$$\Delta_S((i,j),(i,\ell))=c_j+c_\ell. \tag{1}$$

Indeed, precisely the selected vertices in columns $j$ and $\ell$ contribute, each by one. Similarly, for $i\ne h$,

$$\Delta_S((i,j),(h,j))=r_i+r_h. \tag{2}$$

When both coordinates differ, the exact identity is

$$\begin{aligned} &\Delta_S((i,j),(h,\ell))\\ &\quad=r_i+r_h+c_j+c_\ell\\ &\qquad-2a_{i\ell}-2a_{hj}. \end{aligned} \tag{3}$$

To see this, the selected endpoints $(i,j)$ and $(h,\ell)$ contribute two each. A selected vertex in exactly one of the four indicated layers contributes one. The two cross-corners $(i,\ell)$ and $(h,j)$ contribute zero, although the sum of the four layer counts counts each twice. All remaining vertices contribute zero.

2. The lower bound

Put $s=\lceil k/2\rceil$. Any weak $k$-resolving set satisfies $c_j+c_\ell\ge k$ for every two distinct columns, by (1). Let $a=\min_j c_j$.

If $k=2s$ and $a\ge s$, then $|S|\ge ms$. If $a<s$, every other column contains at least $2s-a$ selected vertices, so

$$\begin{aligned} |S|&\ge a+(m-1)(2s-a)\\ &=ms+(m-2)(s-a)\ge ms. \end{aligned}$$

If $k=2s-1$ and $a\ge s$, then again $|S|\ge ms$. Otherwise write $a=s-1-b$ with an integer $b\ge0$. Every other column contains at least $s+b$ selected vertices. Hence

$$\begin{aligned} |S|&\ge s-1-b+(m-1)(s+b)\\ &=ms-1+(m-2)b\ge ms-1. \end{aligned}$$

Thus both asserted values are lower bounds.

3. A cyclic construction attaining the bound

Choose column sizes $q_0,\ldots,q_{m-1}$ as follows:

$$q_j= \begin{cases} s-1,&k\text{ odd and }j=0,\\ s,&\text{otherwise}. \end{cases}$$

Define cumulative offsets and their total by

$$\begin{gathered} T_0=0,\qquad T_{j+1}=T_j+q_j,\\ L=T_m. \end{gathered}$$

In column $j$, select the rows with residues

$$T_j,T_j+1,\ldots,T_{j+1}-1\pmod n. \tag{4}$$

This defines an actual subset of the graph: since $2\le s\le n$, each column size is between $1$ and $n$, so no column repeats a row. Its column counts are exactly $c_j=q_j$, and its cardinality is $L=ms$ for even $k$ and $L=ms-1$ for odd $k$.

Across all columns, the integers used in (4) are exactly $0,1,\ldots,L-1$. Each row therefore occurs either $\lfloor L/n\rfloor$ or $\lceil L/n\rceil$ times. Moreover, $m\ge n+1$ gives $L\ge ns$: this is immediate for even $k$, while for odd $k$,

$$\begin{aligned} L=ms-1&\ge(n+1)s-1\\ &\ge ns. \end{aligned}$$

Consequently every row satisfies $r_i\ge s\ge2$. Every pair of columns satisfies $c_j+c_\ell\ge k$, since all column sizes are $s$, except possibly one of size $s-1$ when $k=2s-1$.

Equations (1) and (2) now give the required inequality for pairs sharing a coordinate: column pairs sum to at least $k$, and row pairs sum to at least $2s\ge k$. For pairs differing in both coordinates, (3) gives

$$\begin{aligned} &\Delta_S((i,j),(h,\ell))\\ &\quad\ge4+k-4=k, \end{aligned}$$

because the two rows contain at least four selected vertices in total, the two columns contain at least $k$, and each cross-corner indicator is at most one. Thus the constructed set is weak $k$-resolving for every stipulated parameter, including $k=3$ and $k=2n$. Its cardinality equals the lower bound, proving the formula. $\square$