Pith. sign in

REVIEW 5 major objections 5 minor 5 references

Multiset Partition Dimension of Graphs

T0 review · 5 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read The paper introduces the multiset partition dimension—the least number of parts in a vertex partition that identifies every vertex by the multiset of its distances to the parts—and claims that every connected graph with at least two vertice

desk verdict New parameter, plausible results, but the central lower-bound proof in Theorem 2.1 does not hold, and every exact value rests on it. read the letter →

arxiv 2607.07407 v3 pith:6JSBPQGN submitted 2026-07-08 math.CO

Azzah Albejani , Yuqing Lin , Joe Ryan , Kiki A. Sugeng This is my paper · ORCID
classification math.CO MSC 05C12
keywords multisetpartitiondimensionresolvingrepresentationmetricgraphdistancespathsandcyclesgridladdergraphs
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 defines a new graph invariant, the multiset partition dimension, which measures the smallest number of parts in a vertex partition such that each vertex is uniquely identified by the unordered list of its distances to the parts. It tries to establish that this number is never below 4 for a connected graph with at least two vertices, and that 4 is attained for several common graph families: paths, cycles of length at least nine, grids, and ladders. If true, this gives a sharp threshold: four unlabeled distance probes can name vertices in these families, while no connected graph can be named with fewer than four probes. The paper also shows that some highly symmetric graphs—complete graphs, wheels, friendship graphs—cannot be resolved at all, and that the gap between this parameter and the multiset metric dimension can be arbitrarily large. A reader should care because it completes a natural multiset analogue of a classical resolvability parameter and raises a structural question about which graphs are resolvable at all.

What carries the argument

The central object is the multiset partition representation r_mp(v|Π), which assigns to each vertex the multiset of distances to the t parts of a partition; a partition is resolving when these multisets are pairwise distinct. The lower-bound machinery is the three-part contradiction argument in Theorem 2.1, which chases shortest paths between boundary vertices to force a collision of representations. For constructions, the paper relies on Lemma 2.1—two vertices with identical distances to every other vertex must lie in different parts—and on partitions that isolate a few small parts plus one large remainder part.

What would settle it

Exhibit a connected graph with at least two vertices and a resolving multiset partition into three parts—i.e., a partition where every vertex has a distinct multiset of distances to the three parts. A brute-force search over all connected graphs up to eight or nine vertices, enumerating all 3-part partitions, would either find such a graph or provide strong evidence that the lower bound is correct.

Watch

Extended reading notes

Core claim

The central claim is that the multiset partition dimension mpd(G), defined by the multiset representation r_mp(v|Π) = {d(v,S_1), ..., d(v,S_t)}, is bounded below by 4: for every connected graph on at least two vertices, mpd(G) ≥ 4. The paper attempts to prove this by showing that any partition into three parts forces two vertices to share the same multiset of distances. It then supplies four-part resolving partitions for paths P_n (n ≥ 5), cycles C_n (n ≥ 9), grids G_{n,m}, and ladders L_m, proving mpd = 4 for these classes; the cycle C_8 is shown to require 5 parts, and C_n with n ≤ 7 is declared to have infinite multiset partition dimension. The paper also constructs graphs with any prescr

Load-bearing premise

The load-bearing premise is that in the proof of Theorem 2.1 one may assume that a shortest path between a vertex v in S1 and a closest vertex t in S2 lies entirely inside S3; if that configuration cannot always be forced, the three-part contradiction argument and the universal lower bound mpd ≥ 4 collapse.

Editorial extensions

If this is right

  • Paths P_n (n ≥ 5), cycles C_n (n ≥ 9), grids G_{n,m} (n ≥ 3, m ≥ 5), and ladders L_m (m ≥ 5) all have multiset partition dimension exactly 4, so the lower bound is tight for several infinite families.
  • Cycles of length at most 7 admit no resolving multiset partition at all, and C_8 requires exactly 5 parts.
  • Complete graphs, wheels, friendship graphs, fan graphs, and t-fold wheels have infinite multiset partition dimension—no finite resolving multiset partition exists for them.
  • For every integer k ≥ 6 (and, with a small modification, k = 5) there exists a graph whose multiset partition dimension is exactly k.
  • The gap between the multiset partition dimension and the multiset metric dimension can be arbitrarily large, so the two parameters are genuinely different.

Reading between the lines

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

  • A testable extension: because the multiset representation discards coordinate order, the lower bound can be read as a statement about unlabeled landmarks—if a resolving partition exists at all, at least four unlabeled distance sensors are needed; simulating random distance multisets on small networks could reveal whether three landmarks ever suffice.
  • The infinite cases (complete graphs, wheels, friendship graphs) all possess local twin-like structures, suggesting a structural conjecture not made in the paper: a connected graph has finite mpd exactly when its twin relation can be neutralized by placing twin vertices in distinct parts—a direct extension of Lemma 2.1 that could be checked computationally.
  • The small-cycle and prism computations hint that non-resolvability is a small-diameter or local phenomenon; a natural next step is to enumerate all connected graphs up to about ten vertices and compute mpd to see whether any 3-part resolving partition exists, which would settle whether the claimed universal lower bound is actually true.
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

5 major / 5 minor

Summary. The paper introduces the multiset partition dimension mpd(G), a variant of partition dimension in which a vertex is identified by the multiset of its distances to the parts of a vertex partition. The main claims are: (i) a universal lower bound mpd(G)≥4 for connected graphs with at least two vertices (Theorem 2.1); (ii) exact values mpd(P_n)=4 for n≥5, mpd(C_n)=∞ for n≤7, mpd(C_8)=5, mpd(C_n)=4 for n≥9, mpd(G_{n,m})=4 for grids with n≥3,m≥5, and mpd(L_m)=4 for ladders with m≥5; (iii) a prism upper bound mpd(P_m)≤6; (iv) a construction showing mpd can be any prescribed integer at least 6; and (v) infinite multiset partition dimension for complete, wheel, friendship, fan, and t-fold wheel graphs. The proofs rely on explicit four-part partitions for upper bounds and on Theorem 2.1 for all lower bounds.

Significance. If the results were fully established, the paper would introduce a natural parameter and provide a useful set of benchmark values. The explicit upper-bound partitions for paths, cycles, grids, and ladders are concrete and checkable, and the novelty of the multiset setting is clear. However, the central lower-bound proof is not rigorous as written, and several exact-value claims are supported by unshown computer searches or informal 'it can be verified' assertions. No reproducible code or certificates accompany the computer claims. With a repaired proof of Theorem 2.1 and complete verification of the asserted distinctions, the paper could make a modest but valid contribution.

major comments (5)
  1. [§2, Theorem 2.1 (proof, p. 3)] The lower bound mpd(G)≥4 is not established. The proof says 'Without loss of generality, assume that a shortest path between v and t contained entirely in S3,' where v∈S3_1 and t∈S2 is closest to v. This cannot hold literally since t∉S3. More importantly, a shortest path between a vertex of S3 and a vertex of S2 may pass through S1 or remain partly in S2, and no reduction is given for those configurations. The subsequent case analysis ('we return to a situation analogous...') does not prove that the new pair has the required form or that a distance strictly decreases in every branch. Therefore the recursive descent is not a valid argument. Since Theorem 2.1 is used to rule out resolving partitions of size 1–3 for every exact value in Section 3, the main exact-value claims currently rest on an unproved bound.
  2. [§3, Theorem 3.2 (cycles)] The cycle exact values are not fully supported. The proof asserts 'we have verified by computer search' for n<9 and 'verified manually' for C9, C10, and C11, but no code, output, or exhaustive case analysis is provided. In particular, mpd(C_n)=∞ for n≤7 requires ruling out all partition cardinalities, not only t=4; the scope of the search is not described. Also, for n≥9 the uniqueness of representations of vertices in S1 is asserted as 'easy to verify' without a proof. Since these are exact values, including an infinite case, the verification needs to be reproducible or replaced by a proof.
  3. [§3, Theorems 3.3 and 3.4 (grids and ladders)] For grids and ladders, the theorem claims 'It can be verified that...' immediately after writing distance formulas. Because the representation is an unordered multiset, injectivity is nontrivial: one must show no two distinct vertices share the same multiset {d1,d2,d3,d4}, where d4 is 0 or 1. The three sources (1,1), (1,2), (1,m) are not symmetrically placed, but a coordinate-wise vector argument is insufficient because the multiset forgets which distance belongs to which source. An explicit inequality proof or a finite verification for the claimed parameter range is required.
  4. [§3, Theorem 3.5 and prism discussion] The prism upper bound mpd(P_m)≤6 is supported by the statement 'owing to the asymmetric structure of the other five parts, these representations are all pairwise distinct' with no detailed argument for vertices in S6. The preceding computer verification for m up to 70 is also undocumented. The theorem is only an upper bound, but the pairwise-distinctness claim is load-bearing for that bound and should be proved rather than asserted.
  5. [§2, Theorem 2.2 and Theorem 2.3] The 'Novi tree' construction before Theorem 2.2 is checked by informal statements ('it is easy to see', 'based on the construction of the tree, these two distances are different') with undefined indices such as t and w. Since this underlies the claim that |mpd(G)−md(G)| can be arbitrarily large, a formal verification is needed. In Theorem 2.3, the assertion that all vertices in S_k have unique representations because 'the distance patterns... are different' is also insufficient: with k−1 singleton parts, two vertices on different tails could in principle produce the same multiset of distances. The paragraph about merging parts considers only one illustrative merge, not all partitions that could yield fewer than k parts. Please provide complete proofs.
minor comments (5)
  1. [Throughout] There are numerous typographical errors, e.g., 'the the multiset variant', 'patition' in Figure 6, and 'formup to 70' in the prism discussion.
  2. [§2, Theorem 2.1] The notation S2_1, S3_1, etc. is introduced without precise definitions; Figure 1 is not described in enough detail to make the case analysis readable.
  3. [§3, Theorem 3.2] The phrase 'for cycle with diameter≥6' is confusing: for C9, C10, and C11 the diameter is 4 or 5, and the text says these were manually verified. Please state explicitly for which n the diameter argument applies.
  4. [§3, Theorem 3.1] The assertion that 'each nonzero coordinate increased by n−4−i' is terse; it would be clearer to write explicit formulas for rmp(v_i|Π) for all i rather than relying on a one-sentence monotonicity claim.
  5. [§2, Theorem 2.3] The sentence 'Note, the similar construction can be used to construct a graph with mpd(G)=5' is not proved. Either provide a complete proof or state it as a separate conjecture.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation found; the main lower bound is an attempted contradiction proof, not a fit or self-referential definition. The real weakness is a proof gap, not circularity.

full rationale

Walking the derivation chain from the definition of rmp(v|Π) through Theorem 2.1, no step equates a derived quantity to an input by construction. Theorem 2.1 argues by contradiction on a hypothetical 3-part resolving partition; the disputed WLOG about a shortest path contained entirely in S3 is a correctness gap, not a circular reduction. The upper-bound constructions for paths, cycles, grids, ladders, and prisms directly exhibit partitions and list or compare multiset representations; they do not reuse a fitted parameter or assume the lower bound. Theorem 2.3 constructs graphs with prescribed mpd and verifies distinctness of representations, and the infinite-dimension proofs for complete, wheel, friendship, fan, and t-fold wheel graphs are direct arguments from the definition. The only author-overlapping citation is [4] (Bong and Lin, including Y. Lin), used in Section 2 to supply trees with prescribed multiset metric dimension for the side observation that |mpd − md| can be arbitrarily large. That citation is not used to prove the central mpd ≥ 4 theorem, does not define mpd in terms of md, and is not the input that produces the exact values in Sections 3–4. Thus no circular step can be exhibited; the paper's actual weaknesses are the unproven WLOG in Theorem 2.1 and the asserted computer checks, which are correctness concerns rather than circularity.

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

No numerical free parameters are fitted; the hand-chosen partitions are constructive proof devices rather than fitted constants. The main load-bearing premises are the unjustified WLOG in Theorem 2.1, the unverified computer searches, and the omitted injectivity proofs in the class results.

assumptions (4)
  • ad hoc to paper WLOG: a shortest path between v in S1_3 and t in S2 is contained entirely in S3.
    Used in the proof of Theorem 2.1 to argue that mpd(G)≥4. This is not generally true and is not justified.
  • domain assumption Computer-search verification for C_n (n<9) and prism P_m (m≤70) is correct.
    The exact values for small cycles and the upper bound for prisms rely on claimed computational checks; no algorithm or output is given.
  • ad hoc to paper Injectivity of distance multisets for grid/ladder/prism partitions can be verified by inspection.
    Theorems 3.3, 3.4, and 3.5 assert uniqueness of representations without a complete proof.
  • domain assumption Multiset metric dimension values of Novi trees from [4] are correct.
    Theorem 2.2 uses the multiset dimension of a tree family from the authors' earlier paper to show the gap can be arbitrarily large.
invented entities (1)
  • multiset partition dimension mpd(G)
    purpose: Central new graph invariant: minimum number of parts in a vertex partition such that each vertex has a unique multiset of distances to the parts.
    The parameter is defined in the paper and is internally consistent with examples, but there is no external falsifiable evidence outside the paper's own computations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multiset Partition Dimension of Graphs." pith.science (2026). https://pith.science/paper/6JSBPQGN

@misc{pith2026260707407,
  author       = {Pith},
  title        = {Pith review of: Multiset Partition Dimension of Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6JSBPQGN}},
  note         = {Machine review of arXiv:2607.07407}
}
read the original abstract

In this paper, we introduce the multiset partition dimension of graphs. This parameter extends the classical partition dimension to the multiset setting by considering multiset distances from vertices to parts of a vertex partition. We establish some fundamental properties of this parameter and determine its exact values for several important classes of graphs.

Figures

Figures reproduced from arXiv: 2607.07407 by the authors.

Figure 1
Figure 1. Structure of the graph when mpd=3 3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The partitions are S1 = {L2, L7}, S2 = {L16, L29}, S3 = {L1, L4, L11, L22}, and S4 = V (G) \ (S1 ∪ S2 ∪ S3), resulting in a total of four parts. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. For the graph, the resolving multiset partition [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: For the graph, the resolving multiset partition [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: A graph with mpd = 7. Parts are highlighted by red boxes Theorem 2.3. For any positive integer k ≥ 6, there exists a graph G whose multiset partition dimension is k, that is, mpd(G) = k. Proof. Let k ≥ 6. We construct the graph Gk by taking the complete graph Kk as the…
Figure 6
Figure 6. Figure 6: An example illustrating the multiset partition dimension following the patition schema used in the proof for [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: For the path graph Pn, the partition is illustrated together with the multiset partition representations of vertices, showing that mpd(Pn) = 4. The above partition is not unique, for example, the following is a different partition [PITH_FULL_IMAGE:figures/full_fig_p00…
Figure 8
Figure 8. Figure 8: An example of multiset partition dimension [PITH_FULL_IMAGE:figures/full_fig_p008_8.png]
Figure 9
Figure 9. Figure 9: C8 has mpd = 5, with partitions illustrated in the figure. Note that C8 cannot be resolved with mpd = 4 since the multiset representations of some vertices would contain duplicates. Vertex Multiset partition representation 1 {0, 1, 1, 3, 3} 2 {0, 1, 1, 2, 4} 3 {0, 1, 1…
Figure 10
Figure 10. Figure 10: C9 has mpd = 4, with partitions illustrated in the figure. Vertex Multiset partition representation 1 {0, 1, 2, 4} 2 {0, 2, 3, 3} 3 {0, 2, 3, 4} 4 {0, 1, 4, 4} 5 {0, 1, 3, 4} 6 {0, 1, 2, 3} 7 {0, 1, 2, 2} 8 {0, 1, 1, 3} 9 {0, 1, 1, 4} [PITH_FULL_IMAGE:figures/full_fi…
Figure 11
Figure 11. Figure 11: For the cycle graph Cn with n ≥ 9, the partition is illustrated showing that mpd(Cn), n ≥ 9 = 4. For other graphs, we have.. Theorem 3.3. Let Gn,m be a grid graph with n ≥ 3 rows and m ≥ 4 columns. Then mpd(Gn,m) = 5. Proof. Let Gn,m be a grid graph with n ≥ 3 rows an…
Figure 12
Figure 12. Figure 12: For the grid graph G5,5, the partition Π = {{(1, 1)}, {(3, 1)}, {(1, 4)}, {(1, 5)}, {all remaining vertices}} is illustrated in the figure, and mpd(G5,5) = 5. Theorem 3.4. Let Lm be a ladder graph with 2 rows and m ≥ 4 columns. Then mpd(Lm) = 5. Proof. Let Lm be a lad…
Figure 13
Figure 13. Figure 13: For the ladder graph L5, the partition Π = {{(1, 1)}, {(1, 2)}, {(1, 3),(1, 4)}, {(2, 1),(2, 2),(2, 3)}, {all remaining vertices}} is illustrated in the figure, and mpd(L5) = 5. For a ladder graph Lm with larger m, see [PITH_FULL_IMAGE:figures/full_fig_p014_13.png]
Figure 14
Figure 14. Figure 14: For the ladder graph Lm, the partition Π = {{(1, 1)}, {(1, 2)}, {(1, 3),(1, 4)}, {(2, 1),(2, 2),(2, 3)}, {all remaining vertices}} is illustrated together with the multiset partition representations of all vertices. For the prism graph Pm, we have conducted a computer…
Figure 15
Figure 15. Figure 15: For the prism graph P6, the partition Π = {{(0, 0)}, {(0, 2)}, {(0, 3)}, {(1, 2)}, {(0, 1),(1, 0),(1, 1)}, {all remaining vertices}} and mpd(P6) = 6. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_15.png]
Figure 16
Figure 16. Figure 16: For P7, the partition Π = {S1, S2, S3, S4, S5, S6} is illustrated, showing that mpd(P7) = 6. Theorem 3.5. Let Pm be a prism graph with two m-vertex cycles (m ≥ 8) connected by a layer of vertical edges between the corresponding vertices. Then mpd(Pm) ≤ 6. Proof. Let P…
Figure 17
Figure 17. Figure 17: For the prism graph Pm, with m ≥ 8, the partition Π = {S1, S2, S3, S4, S5, S6} is illustrated, showing that mpd(Pm) ≤ 6. The fixed representations of the vertices in S1, S2, S3, S4, S5 are shown. It is not clear if for larger m, the mpd(Pm) could be smaller. Thus, we …

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 1 linked inside Pith

  1. [1]

    The multiset dimension of graphs,

    R. Simanjuntak, P. Siagian, and T. Vetrik, “The multiset dimension of graphs,”arXiv preprint arXiv:1711.00225, 2017

    arXiv 2017

  2. [2]

    Leaves of trees,

    P. J. Slater, “Leaves of trees,”Congr. Numer., vol. 14, pp. 549–559, 1975

    1975

  3. [3]

    On the metric dimension of a graph,

    F. Harary and R. A. Melter, “On the metric dimension of a graph,”Ars Combin., vol. 2, pp. 191–195, 1976

    1976

  4. [4]

    Some properties of the multiset dimension of graphs,

    N. H. Bong and Y . Lin, “Some properties of the multiset dimension of graphs,”Electron. J. Graph Theory Appl., vol. 9, no. 1, pp. 215–221, 2021

    2021

  5. [5]

    Resolvability in graphs and the metric dimension of a graph,

    G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,”Discrete Applied Mathematics, vol. 105, no. 1–3, pp. 99– 113, 2000. 19

    2000

Pith tools

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