Pith. sign in

REVIEW 2 major objections 4 minor 12 references

Metric Dimension of a Direct Product of Three Complete Graphs: The Middle Cone Family

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

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

Pith's one-line read For a three-clique product in the middle cone, the metric dimension is exactly $2(n_3+1)-1$.

desk verdict Solid middle-cone result with explicit resolving sets, but the paper must clarify its relation to [GJ24] and fix a repairable but real gap in Theorem 2.5's case analysis. read the letter →

arxiv 2507.16169 v1 pith:SVY7LCJW submitted 2025-07-22 math.CO

Briana Foster-Greenwood , Christine Uhl This is my paper · ORCID
classification math.CO MSC 05C6905C1205B3005C15
keywords metricdimensionresolvingsetdirectproductgraphcompleteedge-coloredhypergraphforbiddensubgraphlocation-dominationmiddlecone
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

This paper determines exactly how many landmarks are needed to identify every vertex of a direct product of three complete graphs when the three factors are not necessarily the same size but fall in the 'middle cone' region, defined by $3\max(n_1,n_2) \le 2n_3 \le n_1n_2$. It proves that for $K_{n_1+1} \times K_{n_2+1} \times K_{n_3+1}$ in this region, the metric dimension is $2(n_3+1)-1$, and the same number solves the location-domination and location-total-domination problems. The proof goes through an explicit construction of minimum resolving sets and a criterion that reduces 'does this set resolve?' to avoiding a finite list of forbidden subgraphs in an edge-colored hypergraph. Exact metric dimension is known for very few infinite families of graph products, so this adds a substantial family and a reusable verification technique.

What carries the argument

The key object is the landmark graph $G(W)$, a 3-edge-colored hypergraph whose vertices are the landmarks and whose hyperedges record sets of landmarks sharing a fixed coordinate value; colors correspond to the three factor coordinates. A basic landmark system is a set $W$ whose landmark graph has a full set of $n_i$ hyperedges of color $i$, all hyperedges of size at least two, and cross-color intersections of size at most one. The paper proves that such a system resolves $K(\mathbf{n})$ exactly when $G(W)$ avoids three forbidden configurations (bad 4-cycle, plain hex, shark teeth), and that adding a triple loop (a new vertex with a brand-new coordinate in every position) preserves resolvability exactly when a fourth configuration, the rainbow 2-2-triangle, is also absent. The middle-cone construction is engineered so that blue and green hyperedges are poofy (size at least three) and pink hyperedges are sticks of size two, which automatically rules out shark teeth, plain hexes, and rainbow 2-2-triangles, leaving only the bad-4-cycle check.

What would settle it

Compute, for any triple in the middle cone, the distance vectors from the explicitly constructed set $W \cup \{u\}$ to all vertices of $K(\mathbf{n}+\mathbf{1})$; if two distinct non-landmark vertices share a vector, the set fails to resolve and the main theorem is false for that triple. A more fundamental falsifier would be any basic landmark system avoiding the three forbidden subgraphs that still fails to resolve, which would disprove Theorem 2.5 and with it the sufficiency half of the method.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4.6: if $3\max(n_1,n_2) \le 2n_3 \le n_1n_2$, then the direct product graph $K_{n_1+1} \times K_{n_2+1} \times K_{n_3+1}$ has metric dimension $2(n_3+1)-1$. Theorem 4.8 adds that the location-domination number and the location-total-domination number equal the same value, and the explicitly constructed resolving sets are minimum total-dominating sets. The main technical discovery is the characterization in Theorem 2.5: a basic landmark system (a set whose 3-edge-colored hypergraph of equal-coordinate classes has full color classes, no singleton edges, and at most one vertex in any cross-color intersection) resolves the graph if and only if its landmark hypergraph contains no bad 4-cycle, plain hex, or shark teeth. Extending this to triple-looped systems in Theorem 2.7 lets the authors pass from $K(\mathbf{n})$ to $K(\mathbf{n}+\mathbf{1})$ by adding a single new landmark, which is the step that turns the construction into an optimality proof.

Load-bearing premise

The load-bearing premise is that a basic landmark system resolves the graph whenever its associated 3-edge-colored hypergraph avoids bad 4-cycles, plain hexes, and shark teeth; the sufficiency proof is a long case analysis, and the no-poofy-edge part is delegated to the earlier paper rather than proved here, so an unhandled subcase there would break the construction's claim to be resolving.

Editorial extensions

If this is right

  • For every triple in the middle cone, the metric dimension, location-domination number, and location-total-domination number of $K_{n_1+1} \times K_{n_2+1} \times K_{n_3+1}$ all equal $2(n_3+1)-1$, so a single count answers all three locating problems.
  • The constructed resolving sets are explicit and of size $2n_3+1$, meaning a minimum landmark set can be written down directly from the three parameters without search.
  • Because these graphs have diameter two, the equality of metric and adjacency dimension for diameter-two graphs gives the adjacency dimension as $2(n_3+1)-1$ as well.
  • The forbidden-subgraph certificate is independent of the construction: any basic landmark system avoiding the named configurations resolves, which could simplify verification of other candidate sets.
  • The upper cone provably cannot be handled by basic landmark systems of $2n_3$ vertices, while the lower cone remains open, marking the middle cone as the exact region where this particular technique succeeds.

Reading between the lines

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

  • The forbidden-subgraph certificate could be turned into an algorithmic test: build the landmark hypergraph of a candidate set and check for the three (or four, with a triple loop) configurations; if none appear, the set is resolving. The paper does not spell this out.
  • The design principle of Construction 3.1—one color class of hyperedges as sticks and the other two as poofy edges—might be adjustable for parts of the lower cone, where multiple colors of sticks are forced by the pigeonhole principle; the paper leaves this open.
  • The triple-loop extension suggests an inductive lifting pattern: a resolving set for $K(\mathbf{n})$ that avoids rainbow 2-2-triangles can be extended by one all-new-coordinate vertex to resolve $K(\mathbf{n}+\mathbf{1})$, so the middle-cone result may be the base of a longer chain of exact values beyond the cone.
  • Using the paper's publicly available SageMath code, one could test the construction near the middle-cone boundary to see whether the exactness persists or fails, giving evidence about where the cone boundaries actually lie.
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.

Referee Report

2 major / 4 minor

Summary. The paper studies the metric dimension and locating parameters of direct products of three complete graphs K_{n1+1} × K_{n2+1} × K_{n3+1} when the parameter triple lies in the "middle cone," i.e., 3 max(n1,n2) ≤ 2n3 ≤ n1n2. The main results, Theorems 4.6 and 4.8, assert that for this family the metric dimension, the location-domination number, and the location-total-domination number all equal 2(n3+1)−1. The proof strategy is: use a lower bound from prior work [FGU24]; introduce a "basic landmark system" and characterize when such a system resolves the graph in terms of three forbidden subgraphs in an associated 3-edge-colored hypergraph (Theorem 2.5); give an explicit construction of 2n3 landmarks (Construction 3.1); verify that the construction avoids the forbidden subgraphs (Corollary 4.5); and then extend by adding a triple loop. Explicit minimum resolving sets are described, and SageMath code is provided for verifying examples.

Significance. If the main theorem is correct, the paper gives exact metric dimension and locating-total-domination numbers for a genuinely new infinite family of direct products of non-isomorphic complete graphs, generalizing the authors' earlier result for three isomorphic factors. The construction of explicit minimum resolving sets and the extension to locating parameters are useful and concrete. The paper also supplies reproducible SageMath verification code for the finite examples. The central weakness is the proof of the characterization theorem, which contains an incomplete case analysis; this proof is load-bearing because the construction is certified through it.

major comments (2)
  1. [Section 2.4, proof of Theorem 2.5, Case 1, Subcase 1.2] The case split is incomplete. The proof asserts that with exactly three vertices outside the common poofy blue edge, each footprint must have one stick entirely outside and one stick with one endpoint inside the blue edge. This is false: two sticks of different colors may both lie entirely outside the blue edge and share one outside vertex, e.g., G={x,y} and P={y,z}, which still covers all three outside vertices and is locally consistent with Definition 2.1. The proof does not analyze this configuration. I do not believe this yields a counterexample to the theorem: if β's footprint also covers {x,y,z}, then the same-color disjointness of hyperedges forces β to reuse one of α's sticks, after which the other stick cannot cover the remaining outside vertex, so α=β. But that argument is absent. Since Corollary 4.5 invokes Theorem 2.5 to certify the resolving sets, this missing case must be supplied. In addition, the proof should clarify whether the subcase counts all vertices of W outside the blue edge or only vertices in the two footprints' common covered set; under the former reading a further argument is needed to show that every such outside vertex is covered by both footprints.
  2. [Section 2.4 / Section 2.5] A similar unhandled pattern occurs in Subcase 1.2: the proof assumes that each of α's two sticks has exactly one endpoint outside the blue edge. But a footprint can also cover two outside vertices with one stick lying entirely outside and the other stick straddling the blue edge. That alternative is not analyzed. As with Subcase 1.3, same-color disjointness of hyperedges appears to force α=β when β's footprint must match, but the proof does not say so. Theorem 2.7 then says it follows the same main cases as Theorem 2.5, so the gap propagates to the triple-looped extension used in Corollary 4.5. The revision should either fill these cases directly or state and prove a small auxiliary lemma covering the "both sticks outside" patterns in both theorems.
minor comments (4)
  1. [Section 2.3] In the sentence defining footprints, "W1,a1 ∪ W2,a2 ∪ Wa3" should read "W1,a1 ∪ W2,a2 ∪ W3,a3".
  2. [Theorem 4.8] The theorem statement uses "location-domination, and total-location-domination numbers" while the surrounding text uses "location-total-domination number"; the terminology should be made consistent.
  3. [Theorem 2.5] The no-poofy-edge case is dismissed by reference to [FGU24, proof of Theorem 9]. A one-sentence explanation of why that proof applies when the global landmark graph contains poofy edges elsewhere would help the reader assess the generalization.
  4. [Table 2] The figure for Case 1.3 illustrates only the pattern where one stick is outside and one stick straddles the blue edge; the alternative pattern (both sticks outside, sharing a vertex) should either be added to the figure or explicitly discussed in the text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the resolving-set certificate is produced by an independent iff characterization, and the self-citations used are published theorems that do not assume the target equality.

full rationale

The derivation chain is self-contained. Theorem 4.6 combines the lower bound dim(K(n+1)) >= 2n3+1 from [FGU24, Theorem 2] with the upper bound dim(K(n+1)) <= 2n3+1 from Corollary 4.5. The upper bound is obtained by constructing W explicitly in Construction 3.1, proving W is a basic landmark system (Proposition 4.3), proving its landmark graph avoids bad 4-cycles (Lemma 4.4), observing that shark teeth, plain hexes, and rainbow 2-2-triangles are impossible because only pink sticks exist (Lemma 4.2), and then applying the independent iff characterization Theorem 2.5 and its triple-loop analogue Theorem 2.7. No parameter is fitted: q, r, f, and all multiplicities are explicit integer functions of n. The forbidden-subgraph characterization is proved, not defined, and the construction is checked against it rather than the reverse. The lower-bound self-citation [FGU24, Theorem 2] is a published theorem whose assumptions do not include the middle-cone equality, so it is independent support rather than a circular premise. The possible incompleteness of Subcase 1.3 in the proof of Theorem 2.5 flagged by the skeptic is a correctness/completeness concern, not circularity: it does not make any equation an input to itself. The equality of location-domination and location-total-domination numbers in Theorem 4.8 follows from the independent facts that W union {u} is minimum resolving (Theorem 4.6) and total-dominating (Lemma 4.7), so no fitted or self-referential quantity appears there either.

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

No free parameters were fitted: every auxiliary quantity in Construction 3.1 is an explicit function of n1, n2, and n3. The main theorem depends on a published lower bound from the authors' prior work and on a detailed case analysis, but not on any data fitting or newly postulated physical entity.

assumptions (4)
  • domain assumption dim(K(n)) ≥ 2n3-1 for all n in N ([FGU24, Theorem 2]).
    Imported from the authors' earlier published paper; used as the lower bound in Theorem 4.6. If it failed for any middle-cone parameter, the formula would only be an upper bound.
  • domain assumption The no-poofy-edge case of Theorem 2.5 is exactly handled by the proof of [FGU24, Theorem 9].
    Section 2.4, proof of Theorem 2.5: footprints without poofy edges are resolved by a prior proof. This delegation is load-bearing because the new case analysis starts only after that case is set aside.
  • domain assumption SageMath code used to verify the examples in Section 5 is correct.
    The paper states that the examples can be checked by computer and links a repository, but does not include the verification in the text. These examples are not central to Theorem 4.6.
  • domain assumption Metric dimension equals adjacency dimension for graphs of diameter two ([JO12]).
    Used in the introduction to transfer the metric-dimension result to adjacency dimension; not load-bearing for the main theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Metric Dimension of a Direct Product of Three Complete Graphs: The Middle Cone Family." pith.science (2026). https://pith.science/paper/SVY7LCJW

@misc{pith2026250716169,
  author       = {Pith},
  title        = {Pith review of: Metric Dimension of a Direct Product of Three Complete Graphs: The Middle Cone Family},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SVY7LCJW}},
  note         = {Machine review of arXiv:2507.16169}
}
read the original abstract

In previous work, we determined the metric dimension for a direct product of three isomorphic complete graphs. Turning to the case where the complete graphs may have different orders, there are three families we refer to as the upper, lower, and middle cones. We determine the metric dimension and location-total-domination number for a family of direct products of three complete graphs stemming from the middle cone. We explicitly describe minimum resolving sets. To verify the sets are resolving, we define a basic landmark system and show it will be a resolving set if and only if its associated 3-edge-colored hypergraph avoids three types of forbidden subgraphs. This generalizes the technique used for three isomorphic factors.

Figures

Figures reproduced from arXiv: 2507.16169 by the authors.

Figure 1
Figure 1. Landmark graph G(W) of a minimum resolving set for K(4, 5, 7). Landmarks in the same blue (solid) hyperedge have the same first coordinate; landmarks connected by a green (dotted) edge have the same second coordinate; and landmarks connected by a pink (dashed) edge have the same third coordinate. to W) is the subgraph of G(W) induced by the set of edges {W1,a1 , W2,a2 , W3,a3 }. The elements of W1,a1 ∪W2,a2 ∪Wa3 are… view at source ↗
Figure 2
Figure 2. Landmark graph G(W) of a resolving set of size 16 for K(3, 3, 8). always successful though, and the challenge is finding unified and easy to describe constructions. Code. The examples mentioned in this section can be checked by computer. Our code for verifying resolving sets of K(n) with SageMath [The22] is available at https://github.com/fostergreenwood/metric-dimension. References [CHM+07] Jos´e C´aceres, Carmen H… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 10 canonical work pages

  1. [1]

    Pelayo, Mar\' a L

    Jos\' e C\' a ceres, Carmen Hernando, Merc\` e Mora, Ignacio M. Pelayo, Mar\' a L. Puertas, Carlos Seara, and David R. Wood. On the metric dimension of C artesian products of graphs. SIAM J. Discrete Math. , 21(2):423--441, 2007. https://doi.org/10.1137/050641867 doi:10.1137/050641867

    doi:10.1137/050641867 2007

  2. [2]

    Metric D imension of a D irect P roduct of T hree C omplete G raphs

    Briana Foster-Greenwood and Christine Uhl. Metric D imension of a D irect P roduct of T hree C omplete G raphs. Electron. J. Combin. , 31(2):Paper No. 2.13, 2024. https://doi.org/10.37236/12399 doi:10.37236/12399

    work page doi:10.37236/12399 2024

  3. [3]

    On the Metric Dimension of $K_a \times K_b \times K_c$

    Valentin Gledel and Gerold Jäger. On the metric dimension of k_a k_b k_c , 2024. URL: https://arxiv.org/abs/2408.17229, https://arxiv.org/abs/2408.17229 arXiv:2408.17229

    work page Pith review arXiv 2024

  4. [4]

    The metric dimension of Z _n Z _n Z _n is 3n/2

    Gerold Jäger and Frank Drewes. The metric dimension of Z _n Z _n Z _n is 3n/2 . Theoretical Computer Science , 806:344--362, 2020. URL: https://www.sciencedirect.com/science/article/pii/S0304397519304098, https://doi.org/10.1016/j.tcs.2019.05.042 doi:10.1016/j.tcs.2019.05.042

    work page doi:10.1016/j.tcs.2019.05.042 2020

  5. [5]

    New Optimal Results on Codes for Location in Graphs

    Ville Junnila, Tero Laihonen, and Tuomo Lehtilä. New optimal results on codes for location in graphs, 2025. URL: https://arxiv.org/abs/2306.07862, https://arxiv.org/abs/2306.07862 arXiv:2306.07862

    work page Pith review arXiv 2025

  6. [6]

    The metric dimension of the lexicographic product of graphs

    Mohsen Jannesari and Behnaz Omoomi. The metric dimension of the lexicographic product of graphs. Discrete Math. , 312(22):3349--3356, 2012. https://doi.org/10.1016/j.disc.2012.07.025 doi:10.1016/j.disc.2012.07.025

    work page doi:10.1016/j.disc.2012.07.025 2012

  7. [7]

    Dorota Kuziak, Iztok Peterin, and Ismael G. Yero. Resolvability and strong resolvability in the direct product of graphs. Results Math. , 71(1-2):509--526, 2017. https://doi.org/10.1007/s00025-016-0563-6 doi:10.1007/s00025-016-0563-6

    work page doi:10.1007/s00025-016-0563-6 2017

  8. [8]

    Dorota Kuziak and Ismael G. Yero. Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, 2021. URL: https://arxiv.org/abs/2107.04877, https://doi.org/10.48550/ARXIV.2107.04877 doi:10.48550/ARXIV.2107.04877

    arXiv doi:10.48550/arxiv.2107.04877 2021

Show all 12 references
  1. [9]

    Eigenspaces of H amming graphs and unitary C ayley graphs

    Torsten Sander. Eigenspaces of H amming graphs and unitary C ayley graphs. Ars Math. Contemp. , 3(1):13--19, 2010. https://doi.org/10.26493/1855-3974.100.7f8 doi:10.26493/1855-3974.100.7f8

    2010 doi

  2. [10]

    Tillquist, Rafael M

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

    2023

  3. [11]

    S ageMath, the S age M athematics S oftware S ystem ( V ersion 10.6) , 2022

    The Sage Developers . S ageMath, the S age M athematics S oftware S ystem ( V ersion 10.6) , 2022. https://www.sagemath.org . https://doi.org/10.5281/zenodo.593563 doi:10.5281/zenodo.593563

    2022 doi

  4. [12]

    Computing the metric dimension of the categorial product of some graphs

    Tom\'a s Vetr\'ik and Ali Ahmad. Computing the metric dimension of the categorial product of some graphs. Int. J. Comput. Math. , 94(2):363--371, 2017. https://doi.org/10.1080/00207160.2015.1109081 doi:10.1080/00207160.2015.1109081

    2017

Pith tools

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