On the weak $k$-metric dimension of Hamming graphs

Dorota Kuziak; Elena Fernandez; Ismael G. Yero; Manuel Mu\~noz-Marquez; Sandi Klavzar

REVIEW 2 major objections 4 minor 14 references

On the weak $k$-metric dimension of Hamming graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every n≥3 and 2≤k≤2n, the weak k-metric dimension of the square Hamming graph is exactly ceil(4n/3) for k=2, n·ceil(k/2) for k=3 or even k, and n·ceil(k/2)−1 for odd k≥5.

desk verdict The main theorem is not proven as written: the k=3 lower bound rests on a false counting claim and the k=2 lower bound fails at n=7, though the even-k cases and the ILP work are solid. read the letter →

arxiv 2505.19642 v1 pith:LSGVW3DH submitted 2025-05-26 math.CO

Elena Fernandez , Sandi Klavzar , Dorota Kuziak , Manuel Muñoz-Marquez , Ismael G. Yero This is my paper · ORCID

classification math.CO MSC 05C1205C7690C05

keywords weakk-metricdimensionk-resolvingsetsCartesianproductsHamminggraphsmetricintegerlinearprogramminghypercubes

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper determines, for every $n\ge 3$ and every feasible $k$ from $2$ to $2n$, the weak $k$-metric dimension of the square Hamming graph $K_n\,\square\,K_n$: the smallest set of vertices that separates every pair of vertices by summing, over the set, the absolute differences of distances, with the sum required to be at least $k$. The value is $\lceil 4n/3\rceil$ for $k=2$, $n\lceil k/2\rceil$ for $k=3$ or $k$ even, and $n\lceil k/2\rceil-1$ for odd $k\ge 5$, thereby complementing the $k=1$ value known from classical metric dimension. The upper bounds come from explicit constructions, and the lower bounds from layer-counting arguments. The paper also improves the integer linear programming formulation for the rectangular Hamming graphs $K_n\,\square\,K_m$, solving its tested instances quickly and supporting two conjectures for that general case.

What carries the argument

The central mechanism is the layer structure of $K_n\,\square\,K_n$: the vertex set is $\mathbb{Z}_n\times\mathbb{Z}_n$, split into $n$ vertical layers $iK_n$ and $n$ horizontal layers $K_n^j$, each a clique. The distance between two vertices is 0, 1, or 2 depending on how many coordinates differ, so the weak $k$-resolving sum for a pair with one equal coordinate is exactly the number of selected vertices in the two corresponding layers, and for a non-aligned pair it counts contributions from four layers minus coincidences at the two intersection vertices. The upper-bound constructions are diagonal sets $D_i=\{(i+r,r): r\in\mathbb{Z}_n\}$; deleting the right number of diagonals leaves the required per-layer counts. The improved ILP formulation $F_{gh}$ aggregates variables by layers, with $h_j$ for horizontal and $g_i$ for vertical layers, and for $k\ge 4$ it drops the non-aligned-pair constraints altogether via Proposition 4.1.

What would settle it

Run an exhaustive computation on $K_3\,\square\,K_3$: the theorem says $\mathrm{wdim}_3=6$, so a 5-vertex weak 3-resolving set would refute the $k=3$ case; checking all $n\ge 3$ for a weak 3-resolving set of size $2n-1$ would settle it generally.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for $n\ge 3$ and $2\le k\le 2n$, $\mathrm{wdim}_k(K_n\,\square\,K_n)$ equals $\lceil 4n/3\rceil$ when $k=2$, $n\lceil k/2\rceil$ when $k=3$ or $k$ is even, and $n\lceil k/2\rceil-1$ when $k\ge 5$ is odd. The proof splits by cases: for $k\ge 4$ it builds weak $k$-resolving sets from diagonal families that leave exactly $k/2$ or $(k+1)/2$ selected vertices in each layer; for $k=2$ it uses periodic block patterns; for $k=3$ it takes the upper bound from the $k=4$ case by monotonicity and then argues that every layer needs at least one selected vertex, ruling out a resolving set of size $2n-1$. The same framework proves the feasibility bound $\kappa(K_n\,\square\,K_m)=2m$ when $n\ge m$, so in the square case $2\le k\le 2n$ is the entire nontrivial range.

Load-bearing premise

The proof that no weak 3-resolving set of $K_n\,\square\,K_n$ can have fewer than $2n$ vertices depends on a precise count of how many selected vertices must lie in the union of two particular rows/columns of the grid; if that count is not exactly as the paper states, the $k=3$ part of the theorem is not established.

Editorial extensions

If this is right

For every $n\ge 3$ the family $K_n\,\square\,K_n$ now has a closed-form weak $k$-metric dimension for every feasible $k$, leaving no gap between $k=2$ and $k=2n$.
The $k=3$ value $2n$ equals the $k=4$ value, so weakening the threshold from 4 to 3 does not reduce the required number of selected vertices in the square Hamming graph.
The ILP formulation $F_{gh}$, which removes the non-aligned-pair constraints for $k\ge 4$, solves the reported $K_n\,\square\,K_m$ instances for $k\ge 4$ in under five seconds, making exact values computationally accessible for larger rectangular Hamming graphs.
If Conjecture 6.1 holds, then for $m\ge n+1$ and $k\ge 3$ the value $\mathrm{wdim}_k(K_n\,\square\,K_m)$ depends only on $m$ and $k$, following the pattern $m\lceil k/2\rceil$ for even $k$ and $m\lceil k/2\rceil-1$ for odd $k$; the computational tables match this for all tested instances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the diagonal and layer-counting techniques likely extend to higher-dimensional Hamming graphs $K_n^d$, a direction the paper names as future work; if the pattern persists, $\mathrm{wdim}_k(K_n^d)$ would take a similar piecewise-linear form in $n$ and $k$ over the feasible range up to $\kappa=2n^{d-1}$.
Beyond the paper, the redundancy of non-aligned-pair constraints for $k\ge 4$ may hold for any Cartesian product of complete graphs, since the distance structure is coordinate-based; this could simplify ILP formulations for hypercubes and other Hamming graphs.
Beyond the paper, the computational tables show that for $k=3$ in $K_n\,\square\,K_m$ the values sometimes deviate from the conjecture for small $m$, suggesting the small-threshold regime may have its own distinct formula, possibly involving a condition like $m\ge cn$, rather than following the $k\ge 4$ pattern.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the main theorem is not established. The k=3 lower bound in Section 3.2 rests on a false counting claim, and the k=2 lower bound in Section 3.3 has a strict inequality that fails at n=7. The even-k cases and the upper-bound constructions are fine, and the ILP section is genuinely useful.

What's new and good: exact values for k≥4 even, the constructions for the upper bounds, and the ILP formulation Fgh with row/column variables plus the redundancy result for k≥4. That part is clean and the computational study is thorough. The self-citation to [9] for the background definition is not a problem.

The soft spots are load-bearing. In Section 3.2, Case 1, after assuming the unique sparse row and column intersect at (i,j), they pick (x,y)∈Y with x≠i, y≠j. Since every other row and column has exactly two Y vertices, the vertical layer xK_n contains (x,y) plus one more, and the horizontal layer K^y_n contains (x,y) plus one more. The union V(xK_n)∪V(K^y_n)\{(x,y)} therefore contains at most two Y vertices, not three. The claim that some layer must contain three Y vertices does not follow, so the contradiction collapses and wdim_3 ≥ 2n is unproved. In Section 3.3, the inequality |E(GY)| ≥ 2n−1−⌊(n−1)/2⌋ > ⌈4n/3⌉ becomes 10 > 10 at n=7, so the exclusion of a K2 component is not proved for that n. Both gaps are central to the theorem.

I am not saying the formula is false; it may well be true. But the paper as written does not prove it. The ILP material could stand alone and be published almost as is. If the authors fix the k=3 counting and handle n=7 in the k=2 argument, the main result would likely be solid.

Who should read it: anyone working on metric-dimension variants in Cartesian products will find the ILP formulation and the even-k results worth their time. A serious editor should send this to peer review, but the expectation should be major revision, not acceptance in the current form.

Referee Report

2 major / 4 minor

Summary. The paper determines the weak k-metric dimension of the Cartesian product K_n □ K_n for every n ≥ 3 and 2 ≤ k ≤ 2n, proving a piecewise formula involving ceilings. The proof combines diagonal upper-bound constructions with layer-counting lower-bound arguments, and it also proposes an improved ILP formulation for K_n □ K_m and reports computational experiments. I verified the upper-bound constructions and the ILP reduction, but found load-bearing errors in the lower-bound proofs for k = 3 and k = 2, so the central theorem is not established as written.

Significance. If the formula were established, it would give the exact weak k-metric dimension for all feasible k in this family, complementing the previously known k = 1 result. The ILP formulation with the reduced constraint set is a useful practical contribution, and the computational experiments support the conjectured formula for rectangular Hamming graphs. However, because the lower bounds for two cases of the main theorem are not proved, the central claim of the paper is currently unsupported.

major comments (2)

[§3.2, Case 1 (proof of wdim_3 ≥ 2n)] In Case 1, the proof considers the pair (x, j) and (i, y) and asserts that, since (i, j) and (x, y) contribute zero, at least three vertices of Y must lie in V(xK_n) ∪ V(K^y_n) \ {(x, y)}. This is false: under the layer-count structure established earlier, xK_n and K^y_n each contain exactly two vertices of Y, both contain (x, y), and their other Y-vertices are distinct, so the union minus (x, y) contains exactly two vertices of Y. Moreover, if (x, j) or (i, y) belongs to Y, that vertex contributes 2, so the required total of 3 can be attained with fewer than three vertices in the union. The asserted contradiction—that one of xK_n or K^y_n contains three vertices of Y—does not follow. Since Case 2 invokes the same “parallel argument”, the lower bound wdim_3(K_n □ K_n) ≥ 2n is not established. This is a load-bearing gap for Theorem 1.1.
[§3.3 (proof of wdim_2 ≥ ⌈4n/3⌉)] After ruling out an isolated vertex, the proof tries to exclude a component isomorphic to K2. The estimate |E(GY)| ≥ 2n − 1 − ⌊(n − 1)/2⌋ > ⌈4n/3⌉ is asserted for all n ≥ 6. For n = 7 the left-hand side is 14 − 1 − 3 = 10 and the right-hand side is ⌈28/3⌉ = 10, so the strict inequality fails. Consequently the argument does not rule out a K2 component for n = 7, and the later step that assumes every component has size at least 3 cannot be applied to n = 7. Since n = 7 is not covered by the preliminary computer check (which covers only n ∈ {3, 4, 5}), the lower bound for k = 2 is missing for n = 7.

minor comments (4)

[§3.1, Case 1] The displayed inequality “4 k/4 − 4 = 2k − 4” is ambiguous and appears to be a typographical error; it should presumably read “4·(k/2) − 4 = 2k − 4” or otherwise be rewritten for clarity.
[§3.3] The preliminary computer check for n ∈ {3, 4, 5} is asserted without details; if it is to be part of the proof, the authors should supply the code or hand-check arguments, and in any case the case n = 7 must be handled explicitly.
[Introduction] The introduction says the result is proved “for any integer n ≥ 2”, while Theorem 1.1 and the abstract state n ≥ 3; this inconsistency should be corrected.
[Section 4] The notation for the formulations alternates between Fs, F−s, and Fgh; making the subscript/superscript notation uniform would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1.1 is a new exact-value computation whose upper and lower bounds are derived by explicit layer counts, not by fitting or by assuming the result.

full rationale

The paper's central result, wdim_k(K_n square K_n) for 2 <= k <= 2n, is obtained through direct combinatorial constructions and lower-bound arguments. The upper bounds for even and odd k are built from explicit diagonal sets X_t and X'_t, and the lower bounds use pigeonhole/layer-counting contradictions; none of these steps is equivalent to the stated formula by construction. The only self-citation of note is Proposition 2.1, quoted as [9, Observation 5], where one author of the present paper is a coauthor. That result is a general identity kappa(G) = min{Delta(x,y)} that follows immediately from the definition of a weak k-resolving set and is not a disguised version of the target formula; it is used only to determine the feasible range k <= 2n. Similarly, the identity dim(G) = wdim_1(G) is cited from [9] only as background and is not used in the proof of Theorem 1.1 for k >= 2. The ILP discussion cites and improves the earlier formulation of [9], but that is an independent computational methodology, not a derivation of the closed-form formula. The weaknesses identified by the reader, namely the false counting claim in Section 3.2 Case 1 and the failing inequality in Section 3.3 for n = 7, are mathematical correctness gaps in lower-bound proofs, not instances of circularity: they do not make the theorem's conclusion an input to its proof. Consequently, no step of the derivation chain reduces to its own inputs, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper introduces no new entities or fitted parameters; it relies on the standard definition of weak k-metric dimension from prior work and the Cartesian product distance formula.

assumptions (2)

standard math Distance in K_n□K_n equals the number of coordinates in which two vertices differ.
Used throughout (Theorem 2.2 and Section 3) to compute Δ_w(x,y) contributions.
domain assumption κ(G) = min{Δ(x,y) : x≠y}, from [9, Observation 5].
Establishes the feasible range 2≤k≤2n for K_n□K_n; taken from the paper that introduced the parameter.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the weak $k$-metric dimension of Hamming graphs." pith.science (2026). https://pith.science/paper/LSGVW3DH

@misc{pith2026250519642,
  author       = {Pith},
  title        = {Pith review of: On the weak $k$-metric dimension of Hamming graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LSGVW3DH}},
  note         = {Machine review of arXiv:2505.19642}
}

abstract

Given a connected graph $G$, a set of vertices $X\subset V(G)$ is a weak $k$-resolving set of $G$ if for each two vertices $y,z\in V(G)$, the sum of the values $|d_G(y,x)-d_G(z,x)|$ over all $x\in X$ is at least $k$, where $d_G(u,v)$ stands for the length of a shortest path between $u$ and $v$. The cardinality of a smallest weak $k$-resolving set of $G$ is the weak $k$-metric dimension of $G$, and is denoted by $\mathrm{wdim}_k(G)$. In this paper, $\mathrm{wdim}_k(K_n\,\square\,K_n)$ is determined for every $n\ge 3$ and every $2\le k\le 2n$. An improvement of a known integer linear programming formulation for this problem is developed and implemented for the graphs $K_n\,\square\,K_m$. Conjectures regarding these general situations are posed.

Figures

Figures reproduced from arXiv: 2505.19642 by the authors.

**Figure 1.** The sets (in bold) X1 (a weak 10-metric basis), X2 (a weak 8-metric basis), X3 (a weak 6-metric basis) and X4 (a weak 4-metric basis), respectively, in K6 □ K6 For this sake, note first that Xt contains precisely k 2 = n − t vertices in each (horizontal and vertical) layer of G. Consider now arbitrary vertices (i, j) and (i ′ , j′ ) of G and distinguish two different situations. If i = i ′ , then in each of the laye… view at source ↗

**Figure 2.** The sets Y6, Y7, and Y8 respectively in K6 □ K6, K7 □ K7, and K8 □ K8 We claim that Yn is a weak 2-resolving set of G. To this end, consider first two vertices with the same first coordinate, say (i, j) and (i, j′ ). Then each of the layers Kj n and Kj ′ n contains at least one vertex of Yn which already implies that ∆Yn ((i, j),(i, j′ )) ≥ 2. Analogously, we see that ∆Yn ((i, j),(i ′ , j)) ≥ 2 for any j and any i ̸… view at source ↗

**Figure 3.** Definition of sets Iuv, Iuv˜, and Iuu˜ Hence, X w∈Iuv sbw = X w∈Iuv˜ sbw + X w∈Iuu˜ sbw − 2sbv − sbu˜ − sbv˜. Therefore 2sbu + 2sbv + X w∈Iuv sbw = 2sbu + 2sbv + X w∈Iuv˜ sbw − sbu˜ − sbv ! + X w∈Iuu˜ sbw − sbv − sbv˜ ! = 2sbu − sbu˜ − sbv˜ + X w∈Iuv˜ sbw + X w∈Iuu˜ sbw . Since the constraints (2a) associated with the pair u, ˜v, and with the pair u, ˜u are both satisfied by sb, we have: sbu + sbv˜ + X w∈Iuv˜ sbw ≥ … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 10 canonical work pages

[9]

Peterin, J

I. Peterin, J. Sedlar, R. ˇSkrekovski, I. G. Yero, Resolving vertices of graphs with differences, Comput. Appl. Math. 43 (2024) article 275

2024
[1]

R. F. Bailey, P. Spiga, Metric dimension of dual polar graphs, Arch. Math. 120 (2023) 467–478. 17

work page 2023
[2]

L. M. Blumenthal, Theory and Applications of Distance Geometry. Oxford University Press (1953)

work page 1953
[3]

C´ aceres, C

J. C´ aceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441

work page 2007
[4]

Dankelmann, J

P. Dankelmann, J. Morgan, E. Rivett-Carnac, Metric dimension and diameter in bipartite graphs, Discuss. Math. Graph Theory 43 (2023) 487–498

2023
[5]

Estrada-Moreno, J

A. Estrada-Moreno, J. A. Rodr ´ ıguez-Vel´ azquez, I. G. Yero, Thek-metric dimension of a graph, Appl. Math. Inf. Sci. 9 (2015) 2829–2840

work page 2015
[6]

Foster-Greenwood, Ch

B. Foster-Greenwood, Ch. Uhl, Metric dimension of a direct product of three complete graphs, Electron. J. Combin. 31 (2024) article 2.13

work page 2024
[7]

Harary, R

F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195

1976

Show all 14 references

[8]

Kuziak, I

D. Kuziak, I. G. Yero, Metric dimension related parameters in graphs: A survey on combina- torial, computational and applied results, arXiv:2107.04877 [math.CO]

arXiv
[10]

P. J. Slater, Leaves of trees, Cong. Numer. 14 (1975) 549–559

1975
[11]

B. C. Tapendra, S. Dueck, The metric dimension of circulant graphs, Opuscula Math. 45(1) (2025) 39–51

2025
[12]

R. C. Tillquist, M. E. Lladser, Low-dimensional representation of genomic sequences, J. Math. Biol. 79 (2019) 1–29

2019
[13]

R. C. Tillquist, R. M. Frongillo, M. E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev. 65 (2023) 919–962

2023
[14]

Fico ® xpress solver

Xpress. Fico ® xpress solver. https://www.fico.com/es/products/fico-xpress-solver. 18

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [9]

Peterin, J

I. Peterin, J. Sedlar, R. ˇSkrekovski, I. G. Yero, Resolving vertices of graphs with differences, Comput. Appl. Math. 43 (2024) article 275

2024

[2] [1]

R. F. Bailey, P. Spiga, Metric dimension of dual polar graphs, Arch. Math. 120 (2023) 467–478. 17

work page 2023

[3] [2]

L. M. Blumenthal, Theory and Applications of Distance Geometry. Oxford University Press (1953)

work page 1953

[4] [3]

C´ aceres, C

J. C´ aceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441

work page 2007

[5] [4]

Dankelmann, J

P. Dankelmann, J. Morgan, E. Rivett-Carnac, Metric dimension and diameter in bipartite graphs, Discuss. Math. Graph Theory 43 (2023) 487–498

2023

[6] [5]

Estrada-Moreno, J

A. Estrada-Moreno, J. A. Rodr ´ ıguez-Vel´ azquez, I. G. Yero, Thek-metric dimension of a graph, Appl. Math. Inf. Sci. 9 (2015) 2829–2840

work page 2015

[7] [6]

Foster-Greenwood, Ch

B. Foster-Greenwood, Ch. Uhl, Metric dimension of a direct product of three complete graphs, Electron. J. Combin. 31 (2024) article 2.13

work page 2024

[8] [7]

Harary, R

F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195

1976