pith. sign in

arxiv: 2605.22307 · v1 · pith:K67MFPKXnew · submitted 2026-05-21 · 🧮 math.CO

The weak k-metric dimension of the direct product of complete graphs

Mohammad Farhan , Dorota Kuziak , Ismael G. Yero This is my paper

Pith reviewed 2026-05-22 04:42 UTC · model grok-4.3

classification 🧮 math.CO
keywords weak k-metric dimensiondirect productcomplete graphsresolving setdistance differencegraph identificationmetric dimension
0
0 comments X

The pith

The weak k-metric dimension of the direct product of two isomorphic complete graphs equals an exact formula in nearly all cases and a bound in the rest.

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

This paper determines the weak k-metric dimension for the direct product of two identical complete graphs. The parameter counts the smallest vertex set S such that every pair of distinct vertices produces a distinct positive sum of absolute distance differences to the members of S. The authors derive closed-form expressions for this count across almost every choice of graph order, with a bound supplied for the single remaining family of cases. A sympathetic reader cares because the result gives concrete numbers for how many landmarks are needed to uniquely locate every point in a highly symmetric and densely connected graph product.

Core claim

For the direct product of two isomorphic complete graphs the weak k-metric dimension equals a simple function of the order and the parameter k in every case except one family, where the size of the smallest set that separates all vertex pairs through summed distance differences is instead bounded above or below.

What carries the argument

A weak k-metric resolving set: the smallest vertex subset S for which the scalar sum of absolute distance differences to S is nonzero for every pair of distinct vertices.

If this is right

  • For most orders the number of landmarks needed to identify every vertex is given by a closed formula.
  • The identification cost scales predictably with the size of the complete graphs under the direct product.
  • Only one narrow parameter regime requires a separate bounding argument rather than equality.
  • The distance-summation property suffices to resolve all vertices in these symmetric products.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same distance-summation technique might yield exact values for direct products of non-isomorphic complete graphs.
  • The result could guide the construction of minimal locating sets in networks whose topology contains dense clique factors.
  • Computer checks on small instances outside the paper's exceptional case would quickly confirm the formulas.
  • Extensions to Cartesian or strong products of complete graphs become natural next targets once this symmetric case is settled.

Load-bearing premise

The distance relations inside the direct product of two identical complete graphs are sufficiently regular that the minimal size of a distinguishing set can be counted directly from the structure, except for one narrow range of parameters.

What would settle it

Explicitly enumerate all small candidate sets S in the direct product K_4 × K_4 (or whichever small order falls in the exceptional family) and verify whether the actual weak k-metric dimension matches the paper's claimed exact value or lies inside the stated bound.

Figures

Figures reproduced from arXiv: 2605.22307 by Dorota Kuziak, Ismael G. Yero, Mohammad Farhan.

Figure 1
Figure 1. Figure 1: The weak 2-resolving basis of Kn × Kn for n = 6, 7, 8, respectively and we claim that the set S = D0 ∪ D1 is a weak 3-resolving set of size 2n. Consider two vertices x = (i, j) and y = (i ′ , j) lying in the same horizontal layer. The vertical case behaves similarly by the symmetry of Kn×Kn. The structure of S implies that each layer Li and Li ′ contains exactly two vertices in S, where Proposition 2.2 imm… view at source ↗
Figure 2
Figure 2. Figure 2: The weak 4-resolving set S of Kn × Kn for n = 13 and 14, respectively Proof. To prove such upper bound, we define the set S = {(i, i) : i ∈ [n]} ∪ {(i, i + 2) : i ∈ [n − 2]} ∪ {(2, 1),(3, 2),(n − 1, n − 2),(n, n − 1)} ∪ {(i, i − 1) : i ≡ 2 (mod 4), 6 ≤ i ≤ n − 2} and claim that S is a weak 4-resolving set of size 2n + 1 +  n 4  . See [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The weak (2n − 2t)-resolving set S of Kn × Kn for (n, t) = (14, 5) ensures that ai ′ = |Li ′ ∩ S| ≤ t for every i ′ ̸= i. We first claim that ai ′ = t for every i ′ ̸= i. Suppose otherwise that ai ′′ ≤ t − 1 for some i ′′ ̸= i. Then, we have ai = |S| −X i ′̸=i ai ′ ≥ (tn + 1) − (t − 1) − t(n − 2) = t + 2. Once more, Lemma 5.2 implies ai ′ ≤ t − 1 for every i ′ ̸= i. However, this implies ai = |S| −X i ′̸=i… view at source ↗
Figure 4
Figure 4. Figure 4: The weak (2n − 2t − 1)-resolving set S of Kn × Kn for (n, t) = (14, 5) Moreover, if i ≡ i ′ ≡ 0 (mod t + 1), then there is no j ∈ [n] such that both (i, j) ∈/ S and (i ′ , j) ∈/ S. This property behaves similarly for the layers L j and L j ′ if j ≡ j ′ ≡ 1 (mod t + 1). Consider two vertices x = (i, j) and y = (i ′ , j) lying in the same horizontal layer. The following argument also applies if the two verti… view at source ↗
read the original abstract

The weak $k$-metric dimension of a graph is roughly understood as the cardinality of a smallest set of vertices $S$ of the graph with the property of uniquely recognizing all the vertices of the graph throughout summations of differences of distances to the vertices of $S$. The weak $k$-metric dimension of the direct product of two isomorphic complete graphs is considered in this work. Specifically, the value of such parameter is computed for almost all possibilities of these products and a bound is provided in the remaining case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript determines the weak k-metric dimension of the direct product of two isomorphic complete graphs K_n □ K_n. It computes the exact value via explicit construction of minimal resolving sets using summed distance-difference vectors for all but one parameter regime and supplies an upper bound in the remaining case.

Significance. If the distance formulas and case analysis hold, the result supplies a near-complete determination of this parameter on a natural infinite family of graphs. The orbit-partition technique and verification that chosen sets produce distinct vectors constitute a standard, verifiable approach in metric-dimension studies; the explicit formulas and the single bounded case are strengths.

major comments (1)
  1. [§3.2] §3.2, the argument establishing uniqueness of the summed distance-difference vectors for n ≥ k+2: the partition into orbits under the natural action is used to reduce the check, but the proof sketch does not explicitly verify that the map remains injective when two vertices differ in exactly one coordinate; a short additional sentence confirming the distance formula in that subcase would close the gap.
minor comments (2)
  1. [Abstract] The abstract states the result for 'almost all possibilities' without quantifying the exceptional regime; adding the precise condition on n and k in the abstract would improve readability.
  2. [Results summary] Table 1 (or the summary table of results) lists the exact values but omits the reference to the theorem number that proves each line; cross-references would help readers locate the proofs.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comment on Section 3.2. The suggestion helps clarify the uniqueness argument, and we have incorporated the requested addition.

read point-by-point responses

  1. Referee: [§3.2] §3.2, the argument establishing uniqueness of the summed distance-difference vectors for n ≥ k+2: the partition into orbits under the natural action is used to reduce the check, but the proof sketch does not explicitly verify that the map remains injective when two vertices differ in exactly one coordinate; a short additional sentence confirming the distance formula in that subcase would close the gap.

    Authors: We agree with the referee that an explicit verification for the subcase of vertices differing in exactly one coordinate strengthens the argument. The distance in the direct product K_n □ K_n between such vertices is 2 when they are adjacent in one factor and non-adjacent in the other, which is immediate from the product distance formula. We will insert a single clarifying sentence immediately after the orbit-partition reduction in Section 3.2 to confirm that the summed distance-difference vectors remain distinct in this subcase. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial computation with no reduction to inputs

full rationale

The paper derives the weak k-metric dimension of K_n □ K_n through explicit case analysis on distance vectors. Distances in the direct product are computed from the standard adjacency rule (vertices (u,v) and (u',v') are adjacent iff u≠u' and v≠v'), and resolving sets are verified by showing that summed distance differences distinguish all vertices except in one explicitly bounded parameter regime. This is self-contained combinatorial counting and orbit partitioning under the natural action; no parameter is fitted to data, no result is renamed as a prediction, and no load-bearing step reduces to a self-citation or prior ansatz by the same authors. The central claim is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the paper presumably rests on standard graph-theoretic definitions of distance, direct product, and the weak k-metric dimension without introducing new entities or free parameters visible here.

axioms (1)
  • standard math Standard definitions and distance properties of graphs and their direct products
    The computation relies on established combinatorial properties of complete graphs and their products.

pith-pipeline@v0.9.0 · 5610 in / 1080 out tokens · 63629 ms · 2026-05-22T04:42:22.029966+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

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

    work page 2023

  2. [2]

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

    work page 1953

  3. [3]

    Chartrand, L

    G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105(1-3) (2000) 99–113

    work page 2000

  4. [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

    work page 2023

  5. [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. [6]

    Fernandez, S

    E. Fernandez, S. Klav ˇzar, D. Kuziak, M. Mu˜noz-M´arquez, I. G. Yero, On the weak k-metric dimension of Hamming graphs, Discrete Opt. 60 (2026) article 100945

    work page 2026

  7. [7]

    Foster-Greenwood, Ch

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

    work page 2024

  8. [8]

    Hakanen, V

    A. Hakanen, V . Junnila, T. Laihonen, I. G. Yero, On vertices contained in all or in no metric basis, Discrete Appl. Math. 319 (2022) 407–423

    work page 2022

  9. [9]

    Harary, R

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

    work page 1976

  10. [10]

    Kuziak, I

    D. Kuziak, I. Peterin, I. G. Yero, Resolvability and strong resolvability in the direct product of graphs, Results Math. 71 (1) (2017) 509–526

    work page 2017

  11. [11]

    Metric dimension related parameters in graphs: A survey on combinatorial, computa- tional and applied results, arXiv:2107.04877 [math.CO] (10 Jul 2021)

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

    work page arXiv

  12. [12]

    Peterin, J

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

    work page 2024

  13. [13]

    Prabhu, T

    S. Prabhu, T. J. Janany and S. Klav ˇzar, Metric dimensions of generalized Sierpi´nski graphs over squares, Appl. Math. Comput. 505 (2025), Paper No. 129528

    work page 2025

  14. [14]

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

    work page 1975

  15. [15]

    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. 20

    work page 2023