Pith. sign in

REVIEW 2 major objections 4 minor 12 references

The Multiset Dimension of Graphs: Extremal Values and King Grids

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

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

Pith's one-line read Multiset dimension can equal a graph's vertex count, and the smallest such graphs have order 11; square king grids need exactly four landmarks, while 3×n king strips need one per column.

desk verdict Real results, honestly scoped: the paper disproves a conjecture and resolves two open problems, with the only genuine soft spot being the census completeness behind 'exactly eight'. read the letter →

arxiv 2607.28813 v1 pith:DJ3FNW4I submitted 2026-07-30 math.CO

Jaan Allikvere This is my paper · ORCID
classification math.CO MSC 05C1205C76
keywords multisetdimensionresolvingsetdistancedegreesequencemetrickinggridstrongproductChebyshevexhaustivesearch
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 settles three open questions about the multiset dimension of a graph, the smallest number of unlabeled landmarks whose distance multisets identify every vertex. It shows that the trivial upper bound dim_m(G) ≤ n(G) is attained: exactly eight connected graphs of order 11 have dim_m = n, and no graph of order 2 through 10 does, disproving the conjecture that dim_m(G) ≤ n(G)−1 always holds. It also proves that every n×n king grid with n ≥ 5 needs exactly four landmarks, while a 3×n king strip needs exactly n for n ≥ 6 (with small exceptional values). Since every fixed-height strip grows linearly, the constant answer on squares is a strictly two-dimensional phenomenon. The proofs combine exhaustive computation, a coordinate change that turns Chebyshev distances into half Manhattan distances on a parity sublattice, and finite certificate arguments.

What carries the argument

For the extremal result, the central identity is that the full vertex set is an m-resolving set exactly when the distance degree sequences DDS(v) = (a_0, a_1, ...), where a_i counts vertices at distance i from v, are pairwise distinct. The paper exploits the non-monotonicity of multiset resolvability under deletions of landmarks. For king grids, the key identity is 2 d_∞((x,y),(a,b)) = |u−u'| + |v−v'| in rotated coordinates (u,v) = (x+y−m, x−y), which maps the Chebyshev metric to half the Manhattan metric on a parity sublattice; four boundary inequalities reduce every potentially resolving three-landmark set to two geometric cases with explicit collisions. For strips, the machinery is a min-

What would settle it

Run an independent exhaustive enumeration of all connected graphs of orders through 11 and compute dim_m exactly; if any graph outside the paper's eight satisfies dim_m = n, Theorem 1.1 collapses. Alternatively, find a three-landmark set that multiset-resolves P_5 ⊠ P_5 or any n ≥ 5, which would falsify Theorem 1.2.

Watch

Extended reading notes

Core claim

The paper establishes three theorems. Theorem 1.1: exactly eight connected graphs of order 11 (and none of smaller order) have multiset dimension equal to their order, disproving the 2017 conjecture of Simanjuntak–Siagian–Vetrík that dim_m(G) ≤ n(G)−1 for every graph with finite multiset dimension. Theorem 1.2: dim_m(P_n ⊠ P_n) = 4 for every n ≥ 5, answering a question of Hakanen and Yero. Theorem 1.3: dim_m(P_3 ⊠ P_n) = n for n ≥ 6, with the small values dim_m(P_3⊠P_3)=∞, dim_m(P_3⊠P_4)=5, and dim_m(P_3⊠P_5)=6. The square-grid lower bound is proved by showing that every set of three landmarks admits an explicit collision pair; the strip lower bound uses a finite min-plus transfer certificat

Load-bearing premise

The load-bearing premise for the 'exactly eight' claim is that the exhaustive enumeration of all connected graphs up to order 11 is complete and that the distance encoding never collides; if any isomorphism class was missed, the conclusion could fail.

Editorial extensions

If this is right

  • The conjecture dim_m(G) ≤ n(G)−1 for finite multiset dimension is false; the true universal upper bound is dim_m(G) ≤ n(G), first attained at order 11.
  • Square king grids are fully classified: dim_m(P_n ⊠ P_n) = ∞ for n = 2,3, dim_m(P_4 ⊠ P_4) = 6, and dim_m(P_n ⊠ P_n) = 4 for all n ≥ 5.
  • The height-three king strip is exactly solved: dim_m(P_3 ⊠ P_n) = n for all n ≥ 6, with the small cases determined.
  • For every fixed h ≥ 3, dim_m(P_h ⊠ P_n) = Θ(n), so a rectangle's multiset dimension can remain bounded only if its aspect ratio stays bounded.
  • All eight extremal graphs have diameter 3, girth 3, and trivial automorphism group; whether such graphs exist for infinitely many orders remains open.

Reading between the lines

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

  • The non-monotonicity mechanism behind the counterexamples suggests that unlabeled resolving parameters may often have graphs where the full set resolves but no proper subset does, independent of the specific multiset setting.
  • The Θ(3^n) growth of the extremal admissible family found in the strip analysis hints that the number of truly minimal landmark sets on tall strips may also grow exponentially, although the paper only certifies the candidate family.
  • The blindness lower bound for strips (one landmark covers at most 2h−3 columns) likely extends to other layered strong products, giving linear lower bounds for a wider class of grids.
  • The observed non-monotonicity in the height-4 strip row (5, 6, >6, 6) suggests that the strip dimension is a fluctuating quasi-linear function for h ≥ 4, which could be tested by extending the computed rectangle scan further.
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 multiset dimension dim_m(G). Part I presents an exhaustive computation over all connected graphs of orders 2–11, reporting exactly eight graphs with dim_m(G)=n(G), all of order 11, thereby disproving the conjecture of Simanjuntak–Siagian–Vetrík that dim_m(G)≤n(G)−1. Part II proves that dim_m(P_n ⊠ P_n)=4 for every n≥5, using rotated coordinates and a case analysis showing that every three-landmark set creates a collision. Part III proves dim_m(P_3 ⊠ P_n)=n for n≥6 via a min-plus transfer certificate for the lower bound and an explicit periodic landmark pattern for the upper bound, and derives dim_m(P_h ⊠ P_n)=Θ(n) for every fixed h≥3.

Significance. If correct, the paper resolves two open questions and a conjecture: the trivial upper bound is attained first at order 11; square king grids are resolved by four landmarks for all n≥5; and height-three king strips require one landmark per column. The paper is unusually strong on reproducibility: it ships scanners, verifiers, raw outputs, a full min-plus potential table, and independent re-implementations of the key checks. The explicit graph G1 and the hand-checkable collision table of Lemma 10.2 are valuable. The main caveat is that the exactness claims of Theorem 1.1 are computational and inherit the trust assumptions of the external generator nauty/geng; the paper explicitly acknowledges this. I also found a specific gap in the zigzag case of Lemma 9.1 that needs repair.

major comments (2)
  1. [§9, Lemma 9.1 (zigzag case)] The alleged collision pair P'=(u3, v3+2), Q'=(u3−1, v3+1) does not have the asserted equidistance to p3=(u3−1, v3): the L1 distances are |u3−(u3−1)| + |(v3+2)−v3| = 3 and |(u3−1)−(u3−1)| + |(v3+1)−v3| = 1, respectively. The statement 'both points have L1-distance 2 from p3' is false, so the two vertices do not have equal ordered distance vectors to the three landmarks. Consequently the derivation of relation (9), v1 = v3+1, is unsupported. Since (9) is used to obtain the parametrization (10) and to finish the zigzag case, this is a load-bearing gap in the proof of Theorem 1.2. Please supply a correct collision pair or a different argument establishing (9).
  2. [§4.1 / Theorem 1.1] The exactness and minimality claims — 'exactly eight' graphs and '11 is the smallest order' — rest on the completeness of the geng enumeration. The paper states this explicitly and checks totals against OEIS A001349, but a generator bug that simultaneously omitted one isomorphism class and duplicated another would preserve the total. Because the theorem's headline is the exact count, I ask the revision to provide or describe an independent verification of the order-11 enumeration, or alternatively to state the theorem as conditional on the correctness of nauty/geng. This is a correctness-risk / reproducibility request rather than a claim of an observed error.
minor comments (4)
  1. [§4.2] The DDI distribution at n=11 is stated as '3 244621 4 996380 5 185858 6 9514 7 630 8 93 9 29 10 1 11 8', but these counts sum to 1,437,143, not the stated 1,437,134 DDI graphs in Table 2. Please reconcile the arithmetic.
  2. [§9] In the zigzag proof, the notation 'L1-distance' is used without definition; it is the rotated-coordinate distance |u−u'|+|v−v'|. Please define it at first use.
  3. [§4.1] The command line fragment 'geng -cq 11i/8' is slightly cryptic; please spell out the full invocation, e.g. 'geng -c -q 11 i/8', so that the eight disjoint streams are unambiguous.
  4. [§16, Remark 16.4] The remark is commendably transparent about the local conditions being necessary but not sufficient for resolving. I suggest adding a sentence in Section 15 emphasising that Proposition 15.1 therefore gives only a lower bound, not a characterisation, for m-resolving sets.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: results are proved from first principles or by reproducible exhaustive computation; the geng completeness assumption is an external correctness risk, not a circular step.

full rationale

I walked the claimed derivation chains and found no step that reduces a prediction to its own inputs by definition, fitting, or self-citation. Part I (Theorem 1.1) is an exhaustive census: the paper explicitly says in §4.1, "Completeness of the enumeration rests on the generator: geng outputs one representative of every isomorphism class of connected graphs," and the later proof uses a sound filter (skip graphs that are not DDI and have no resolving (n−1)-subset) plus exact subset enumeration for survivors. This is a computational claim about external software, not a circular derivation; the OEIS A001349 total match is a consistency check. Proposition 3.1 gives a hand-verified DDI table and the no-proper-subset claim is checked by three independent programs, i.e., reproducible verification rather than assumed conclusion. Part II (Theorem 1.2) is self-contained: Lemma 6.1 proves the rotated-coordinate metric identity; Lemmas 7.1–10.2 construct explicit collision pairs. The only cited ingredient is the upper bound from Hakanen–Yero [5], a different authorship, and the exclusions of dimensions 1 and 2 from [3]; neither is self-citation or a fitted input. Part III (Theorems 1.3 and 1.4) proves the lower bound via necessary local conditions (Lemmas 14.1–14.2) and a finite min-plus transfer certificate V5=V4+1 computed from the admissibility definition; the certificate is not tuned to force the answer, and the paper records that it is not even tight at n=4,5. The upper bound is an explicit period-three landmark pattern proved by shell decomposition. All stated limitations (§5.2, §12, §19) concern open problems or scope, not hidden circular dependencies. No load-bearing self-citation, uniqueness import, renamed known result, or ansatz-via-citation was found.

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

The paper introduces no fitted constants and no new postulated entities. The parity sublattice D_m is a coordinate transformation of the existing king-grid vertex set; the 19-state automaton is a set of 19 pairs of column indicator triples explicitly listed in Appendix A; the min-plus potential V4 is the minimum admissible-prefix weight, uniquely determined by the proven local conditions — none are fitted to force an answer. The only load-bearing external inputs are the correctness of nauty/graph6 enumeration (Part I), two cited prior results ([3], [5]), and the finite certificates' recorded outputs; all are checkable from shipped code.

assumptions (6)
  • domain assumption nauty's geng 2.8.9 and McKay's published graph6 databases enumerate every connected graph up to order 11 exactly once per isomorphism class, with no missed classes.
    Load-bearing for the 'exactly eight' clause of Theorem 1.1. The paper says in §4.1 'Completeness of the enumeration rests on the generator'; the OEIS A001349 total match is a consistency check, not a proof.
  • domain assumption OEIS A001349 counts of connected graphs are correct at orders 2–11.
    Used in §4.1 as the end-to-end check that geng's streams are jointly exhaustive; a wrong OEIS entry would mask an incomplete enumeration.
  • domain assumption Hakanen–Yero upper bound dim_m(P_n ⊠ P_n) ≤ 4 for all n ≥ 5 (their Prop 4.2/Thm 4.3) is correct.
    Theorem 1.2 inherits the upper bound from [5]; the paper only proves the lower bound. Cited prior literature, not re-derived.
  • domain assumption Facts from [3]: only paths have dim_m = 1; no graph has dim_m = 2; a diameter-two graph that is not a path has dim_m = ∞ (for P_3 ⊠ P_3).
    Used in the proof of Theorem 1.2 (excluding dim 1,2) and Theorem 1.3 (dim_m(P_3⊠P_3)=∞ via [3, Thm 3.1]). Cited prior literature.
  • domain assumption The finite outputs recorded by the shipped programs (the V4/V5 certificate, the 184 tight transitions, the 19-state core L, the eigenvector w with Aw=3w, the counts 188/556/44972, the small-case exact values) are accurate.
    Proposition 15.1, Theorem 16.1, Corollary 16.2 and Remark 16.3 rely on these computations; the paper prints the V4 table in Appendix A so the core identity can be checked by hand, and provides verification scripts.
  • standard math Standard results used without proof: Perron–Frobenius theory (Remark 16.3) and basic graph-distance / multiset-representation facts.
    Invoked in Remark 16.3 and throughout; standard mathematical background, not specific to the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Multiset Dimension of Graphs: Extremal Values and King Grids." pith.science (2026). https://pith.science/paper/DJ3FNW4I

@misc{pith2026260728813,
  author       = {Pith},
  title        = {Pith review of: The Multiset Dimension of Graphs: Extremal Values and King Grids},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DJ3FNW4I}},
  note         = {Machine review of arXiv:2607.28813}
}
abstract

We present three results on the multiset dimension of graphs, resolving one conjecture and two open questions from the literature. First, we disprove the conjecture of Simanjuntak, Siagian and Vetr\'ik (2017) that every graph $G$ of order $n(G)$ with finite multiset dimension satisfies $\dim_m(G) \le n(G)-1$: an exhaustive computation over all 1,018,690,328 connected graphs of orders 2 through 11 shows that exactly eight graphs attain $\dim_m(G)=n(G)$, all of order 11, so 11 is the smallest order at which the trivial upper bound is attained. This also answers a question from the recent survey of Farhan, Klav\v{z}ar, Kuziak and Yero. Second, we prove that $\dim_m(P_n \boxtimes P_n)=4$ for every $n \ge 5$, answering a question of Hakanen and Yero: after a $45^\circ$ change of coordinates the Chebyshev metric of the king grid becomes half the Manhattan metric on a parity sublattice, and four boundary inequalities reduce every potentially resolving three-landmark set to two geometric cases, in each of which we exhibit an explicit collision. Third, on king strips the parameter grows linearly: $\dim_m(P_3 \boxtimes P_n)=n$ for $n \ge 6$ (with the small cases determined exactly), where the lower bound rests on three local separation conditions and a finite min-plus transfer certificate whose equality case yields a finite automaton with a 19-state recurrent core, and the upper bound is an explicit landmark pattern of period three that works for every height. Combined with a blindness lower bound, $\dim_m(P_h \boxtimes P_n) = \Theta(n)$ for every fixed $h \ge 3$, so the constant answer on square king grids requires both dimensions to grow.

Figures

Figures reproduced from arXiv: 2607.28813 by the authors.

Figure 1
Figure 1. The graph G1 (graph6 code J?BDf?[hvq_), the first of the eight counterexamples: dimm(G1) = n(G1) = 11. v (a1, a2, a3) v (a1, a2, a3) v (a1, a2, a3) 0 (5, 5, 0) 4 (2, 7, 1) 8 (3, 5, 2) 1 (3, 6, 1) 5 (4, 6, 0) 9 (6, 4, 0) 2 (4, 5, 1) 6 (4, 4, 2) 10 (7, 3, 0) 3 (3, 7, 0) 7 (5, 4, 1) All eleven triples are distinct, so V (G1) is m-resolving. (The table is straightforward to verify from the edge list: for instance vertex… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 1 canonical work pages

  1. [1]

    P. J. Slater,Leaves of trees, Congressus Numerantium14(1975), 549–559

    1975

  2. [2]

    Harary and R

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

    1976

  3. [3]

    Simanjuntak, P

    R. Simanjuntak, P. Siagian, and T. Vetrík,The multiset dimension of graphs, arXiv:1711.00225v2, 2019

    arXiv 2019

  4. [4]

    Hafidh, R

    Y. Hafidh, R. Kurniawan, S. W. Saputro, R. Simanjuntak, S. Tanujaya, and S. Uttunggadewa,Multiset dimensions of trees, arXiv:1908.05879, 2019

    arXiv 1908

  5. [5]

    Hakanen and I

    A. Hakanen and I. G. Yero,Complexity and equivalency of multiset dimension and ID-colorings, Fundamenta Informaticae191(2024), 315–330. doi:10.3233/FI-242185

    work page doi:10.3233/fi-242185 2024

  6. [6]

    Khemmani and S

    V. Khemmani and S. Isariyapalakul,The multiresolving sets of graphs with prescribed multisimilar equivalence classes, International Journal of Mathematics and Mathematical Sciences2018(2018), Article 8978193

    2018

  7. [7]

    Farhan, S

    M. Farhan, S. Klavžar, D. Kuziak, and I. G. Yero,Multiset resolvability parameters in graphs: A survey with new results and open problems, arXiv:2607.10311, 2026

    arXiv 2026

  8. [8]

    Albejani, Y

    A. Albejani, Y. Lin, J. Ryan, and K. A. Sugeng,A survey on multiset dimension and its variations, arXiv:2607.08128, 2026

    arXiv 2026

Show all 12 references
  1. [9]

    G. S. Bloom, J. W. Kennedy, and L. V. Quintas,Some problems concerning distance and path degree sequences, in: Graph Theory (Łagów, 1981), Lecture Notes in Mathematics1018, Springer, Berlin, 1983, pp. 179–190

    1981

  2. [10]

    B. D. McKay and A. Piperno,Practical graph isomorphism, II, Journal of Symbolic Computation60 (2014), 94–112

    2014

  3. [11]

    it/(accessed July 2026)

    B.D.McKayandA.Piperno,nauty and Traces, software, version2.8.9, https://pallini.di.uniroma1. it/(accessed July 2026)

    2026

  4. [12]

    OEIS Foundation Inc.,Entry A001349: Number of connected graphs with n nodes, The On-Line Encyclopedia of Integer Sequences,https://oeis.org/A001349(accessed July 2026)

    2026

Pith tools

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