Pith. sign in

REVIEW 3 major objections 5 minor 3 cited by

Multiset Dimensions of Trees

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

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

Pith's one-line read For finite multiset dimension, every tree of order n is resolved by at most n−2 vertices.

desk verdict The paper's n−2 bound for trees is plausible but the proof has a genuine gap in the even-order, odd-diameter case; the characterizations are a useful step. read the letter →

arxiv 1908.05879 v1 pith:2C72QYYG submitted 2019-08-16 math.CO

Yusuf Hafidh , Rizki Kurniawan , Suhadi Saputro , Rinovia Simanjuntak , Steven Tanujaya , Saladin Uttunggadewa This is my paper · ORCID
classification math.CO MSC 05C1205C05
keywords m-resolvingsetmultisetdimensiontreescaterpillarslobstersgraphdistancescenterofatreeresolving
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

Every tree $T$ with $n$ vertices, diameter at least $2$, and a finite multiset dimension satisfies $md(T)\le n-2$. This proves, for trees, a conjecture that the universal upper bound is $n-1$, and improves it by one. The paper reaches the bound by showing that a smallest resolving set can always be shrunk below the full vertex set, using the center structure of trees and a parity argument. It also gives complete structural characterizations for the two restricted families: caterpillars and lobsters. These are the first tree families for which finiteness of the multiset dimension is decided by simple local conditions.

What carries the argument

The machinery consists of the representation multiset $r_m(v|W)$, the multiset of distances from $v$ to the landmarks in $W$, and an m-resolving set $W$, one that assigns distinct multisets to distinct vertices; $md(G)$ is the minimum size of such a set. The tree proofs lean on the formula $ecc(v)=\mathrm{rad}(T)+d(v,C(T))$, which ties the largest distance from a vertex to its distance from the center, and on a parity count: in a tree of odd diameter, a vertex on one side of the central edge and a vertex on the other side have opposite distances to every third vertex, so the counts of landmarks at odd distance are interchanged. For caterpillars and lobsters, the operating objects are the minimum $k$-center-path and the separation $[H]$ obtained by subdividing every edge incident with the root of a component and deleting the root.

What would settle it

Enumerate all trees of orders 11 and beyond (the paper's tables stop at order 10) and compute their multiset dimensions; the first tree with finite multiset dimension and $md(T)=n-1$ or $md(T)=n$ would disprove Theorem 1. For the specific proof step, test the set $R'=V(T)-N_1-N_2$ in every even-order tree with odd diameter and look for two vertices with the same representation multiset.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central result is Theorem 1: if a tree $T$ of order $n$ and diameter at least $2$ has $md(T)<\infty$, then $md(T)\le n-2$. The proof starts from any resolving set, shows that the full vertex set can be replaced by the complement of the center (or, in the hard odd-diameter even-order case, by the complement of the two centers' neighbor sets), and then shows the remaining set still separates all vertices by their representation multisets. The paper further proves Theorem 2, a necessary-and-sufficient condition for a lobster to have finite multiset dimension in terms of the components left after removing its minimum 2-center path, and Theorem 3, the analogous condition for caterpillars: every vertex of the minimum 1-center path has at most two neighbors outside the path. Together these partially settle the open characterization problem for trees posed in [4].

Load-bearing premise

The main bound rests on the claim that in a tree with odd diameter and even order, deleting the two centers' neighbor sets leaves a landmark set that still distinguishes every vertex by distance multisets; if that separation claim fails, the $n-2$ upper bound is not established.

Editorial extensions

If this is right

  • Conjecture 1 from [4] is true for trees: every tree with finite multiset dimension has $md(T)\le n-1$, and Theorem 1 sharpens this to $md(T)\le n-2$.
  • Since no graph has multiset dimension 2, a non-path tree with finite multiset dimension must have dimension at least 3; Theorem 1 therefore confines its possible values to $1$ and the integers from $3$ through $n-2$.
  • A caterpillar has finite multiset dimension exactly when each vertex of its minimum 1-center path has at most two neighbors outside the path, so the condition can be read off from the spine.
  • A lobster has finite multiset dimension exactly when the components left after deleting its minimum 2-center path are each of a short resolvable shape, with the only allowed infinite one being a star $S_4$; this turns finiteness into a local check.
  • The restriction to a minimum 2-center path is essential: a non-minimum path can satisfy the component conditions while the lobster still has infinite multiset dimension.

Reading between the lines

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

  • Beyond the paper: the parity-counting device used in Theorem 1 should transfer to any bipartite graph with odd diameter and a trackable center structure, so the same deletion argument is a plausible route toward the general $n-1$ conjecture for bipartite graphs.
  • Beyond the paper: because the paper's exhaustive data stop at order 10, the first test of Conjecture 2 is a complete enumeration of trees of orders 11 and 12; if the conjectured bound $n-\mathrm{diam}(T)+1$ is right, no tree of those orders should have dimension larger than that bound.
  • Beyond the paper: the separation-characterization method for lobsters suggests a recursive prescription for wider tree classes built from $k$-center paths, though the paper itself notes that applying the argument inductively to the size of the minimum center-path may be difficult.
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

3 major / 5 minor

Summary. This manuscript studies the multiset dimension md(G) of trees. The main result, Theorem 1, asserts that every tree T of order n and diameter at least 2 with finite multiset dimension satisfies md(T) <= n-2, improving the conjectured upper bound n-1 from [4] for trees. The proof distinguishes even and odd diameter, and within the odd-diameter case separates odd and even order. The authors also state necessary and sufficient conditions for lobsters (Theorem 2) and caterpillars (Theorem 3) to have finite multiset dimension, and they propose Conjecture 2, a sharp bound md(T) <= n - diam(T) + 1, supported by exhaustive computations for trees up to order 10.

Significance. If the main theorem and characterizations are correct, the paper settles Conjecture 1 from [4] for trees in a strengthened form and partially answers Open Problem 1. Theorem 2 is a structurally rich characterization of lobsters and would be a substantial contribution. The exhaustive search data in Table 1, generated with standard tools, provides useful evidence for Conjecture 2 even though the search does not itself constitute a proof. The proofs are direct derivations from the definitions and from basic lemmas in [4], with no apparent circularity. However, the proof of Theorem 1 has a load-bearing gap in the even-order, odd-diameter subcase, and the statement of Theorem 2 contains a definitional ambiguity about S4; both need to be repaired before the claims are fully established.

major comments (3)
  1. [Theorem 1, Case 2.2] In the even-order, odd-diameter subcase of Theorem 1, the set R' = V(T) - N1 - N2 is asserted to be 'the required new m-resolving set' with no proof. The preceding parity argument for the odd-order case relied on |R'| being odd; here, as written, R' contains both centers x and y and has even cardinality, so the stated parity contradiction cannot apply. If the intended set is V(T) - {x,y} - N1 - N2, the text should say so and the resolution proof (for pairs in the same branch and in different branches) must be carried out for the deletion of both neighbor sets. Without this argument, the upper bound md(T) <= n-2 is not established for even-order trees of odd diameter.
  2. [Theorem 2, conditions (2)-(3)] The symbol S4 is used ambiguously. In Section 1, S4 denotes the star on four vertices; in condition (2), a component of G-E(P) that is an S4 has infinite multiset dimension by Lemma 1(4), while in condition (3), S4 appears as one of the allowable component types of [H]. These two uses are not reconciled, and the proof of (2)=>(3) says that an H with infinite multiset dimension 'is an S4 which fulfills (3)' without showing that an S4 component of G-E(P) yields components of [H] of the listed types. The equivalence of (2) and (3) is therefore not demonstrated as written.
  3. [Theorem 2, proof of (3)=>(1)] The proof asserts as an unstated premise that for i=0 and i=n, the maximum resolving set R(Hi) contains a vertex at distance two from P because P is a minimum 2-center path. This is not proved, and it is load-bearing: the subsequent claim that the maximum element of rm(v|union R(Hi)) is ecc(v) depends on it. Without a proof that a vertex at distance two exists in each end component (or a modified construction), the parity arguments in both Constructions 1 and 2 do not go through.
minor comments (5)
  1. [Theorem 1, proof] The first paragraph of the proof contains the typo 'multiset dimention'; it should read 'multiset dimension'.
  2. [Theorem 2, proof of (1)=>(2)] In the sentence 'If there exists a vertex vi in NH(v) with degree at least 4 then there is at least 3 leaves attached to u', the variable should be 'vi' rather than 'u'.
  3. [Theorem 1, Case 2.1] The notation (d(v,x)+1)^{k-1} in the equation for rm(v|R) is not defined; clarify that it denotes a multiset with k-1 copies of the same distance.
  4. [Theorem 2, Construction 1] The component ordering 'S4 > P3 > P2' is informal; define the order explicitly, for example by the number of vertices or by the maximum distance of a vertex in the component to the root.
  5. [Conjecture 2] The statement that the bound is sharp is followed by one example tree; clarify whether sharpness means equality for infinitely many n or for all n, since the bound depends on both n and diameter.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1 is derived from definitions and elementary lemmas, and the self-citations are not load-bearing for the target results.

full rationale

The central derivation (Theorem 1, md(T) <= n-2) proceeds directly from the definition of an m-resolving set and the elementary tree facts in Lemma 3 (radius, centers, eccentricity formula). The only imported results are Lemmas 1 and 2, cited from [4] and [2]; these are basic facts (paths have multiset dimension 1; a twin class of size at least 3 forces infinite multiset dimension) that do not contain or presuppose the n-2 bound, the caterpillar characterization, or the lobster characterization. They are used as small ingredients, not as the conclusion. The reduction from md(T) <= n-1 to md(T) <= n-2 is attempted by explicitly removing one vertex or a neighbor set and re-checking that the remaining set is resolving. The even-order, odd-diameter subcase of Case 2.2 is asserted rather than fully proved, but this is a correctness gap, not a circular reduction: the proposed set is not defined in terms of the conclusion. The exhaustive computer search is explicitly used only to motivate Conjecture 2, not to prove Theorem 1. Theorem 2's equivalence is established by an explicit construction of a resolving set from condition (3) and by deriving condition (2) from a hypothetical resolving set; condition (3) is not defined in terms of finite multiset dimension, so the equivalence is not self-definitional. The note after Theorem 2 about non-minimum 2-center paths is a stated limitation of the chosen path, not a circular step. Overall, no prediction or first-principles claim reduces by construction to its own inputs; self-citations are present but non-load-bearing.

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

No free parameters: the proof is purely combinatorial. The paper depends on standard tree-center facts and on cited lemmas from [4] and [2]. It introduces no new entities. The minimality of the 2-center path is used without proof in Theorem 2.

assumptions (4)
  • standard math In a tree, rad(T)=ceil(diam(T)/2); if the diameter is even then |C(T)|=1, and if odd then C(T)={u,v} adjacent; moreover ecc(v)=rad(T)+d(v,C(T)) (Lemma 3).
    Used repeatedly in Section 2 to compare maximum elements of representations after deleting centers or their neighbors.
  • domain assumption Lemma 1 from [4]: md(G)=1 iff G is a path; no graph has md=2; non-path graphs have md>=3; non-path graphs of diameter at most 2 have md=infinity.
    These prior results are cited, not reproven; they underpin the small-diameter cases and the parity arguments in Theorem 1.
  • domain assumption Lemma 2 from [4,2]: if a vertex has at least two twins (|v*|>=3) then md(G)=infinity.
    Used to bound degrees in Lemma 4 and in Theorem 2, for example deg(u)<=3 and at most two P2 components.
  • ad hoc to paper A minimum 2-center path P has the property that for i=0 and i=n, R(H_i) contains a vertex at distance two from P (used in the (3) implies (1) proof of Theorem 2).
    This minimality property is asserted in the proof construction but not proven; the m-resolving set construction depends on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multiset Dimensions of Trees." pith.science (2026). https://pith.science/paper/2C72QYYG

@misc{pith2026190805879,
  author       = {Pith},
  title        = {Pith review of: Multiset Dimensions of Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2C72QYYG}},
  note         = {Machine review of arXiv:1908.05879}
}
abstract

Let $G$ be a connected graph and $W$ be a set of vertices of $G$. The representation multiset of a vertex $v$ with respect to $W$, $r_m (v|W)$, is defined as a multiset of distances between $v$ and the vertices in $W$. If $r_m (u |W) \neq r_m(v|W)$ for every pair of distinct vertices $u$ and $v$, then $W$ is called an m-resolving set of $G$. If $G$ has an m-resolving set, then the cardinality of a smallest m-resolving set is called the multiset dimension of $G$, denoted by $md(G)$; otherwise, we say that $md(G) = \infty$. In this paper, we show that for a tree $T$ of diameter at least 2, if $md(T) < \infty$, then $md(T) \leq n-2$. We conjecture that this bound is not sharp in general and propose a sharp upper bound. We shall also provide necessary and sufficient conditions for caterpillars and lobsters having finite multiset dimension. Our results partially settled a conjecture and an open problem proposed in [4].

Figures

Figures reproduced from arXiv: 1908.05879 by the authors.

Figure 1
Figure 1. A lobster G with odd diameter. The vertices in the same box will have different representation with re￾spect to R, because R(Hi) is a resolving set for Hi . Now consider vertices in different boxes. Vertices in a box in Side 1 are with the same distance to vertices in M := ∪ n k=i+1R(Hk), but they have distinct multiset repre￾sentations with respect to N := R −M, since the maximum distance to vertices in N is distin… view at source ↗
Figure 2
Figure 2. A lobster G with even diameter. Similar argument from Construction 1 can be applied to prove that the vertices in the same side have distinct representations. Let u and v be vertices with the same eccentricity in Side 1 and side 2, respectively. For i = 0, 1, . . . , ecc(v), we define mv(i) as the multiplicity of i in rm(v|R). If v is in Hn/2+1, then mv := (mv(ecc(v)), mv(ecc(v)−1), mv(ecc(v)−2)) = (a0, a1, a2 + b0 … view at source ↗
Figure 3
Figure 3. Illustration for the case when u ∈ Hn/2−1 and v /∈ Hn/2+1. (1) ⇒ (2) Let R be an m-resolving set of G and suppose that G − E(P) has a component H 6≈ S4 with infinite multiset dimension. Let v be the vertex in H which is also in P. We will prove that there are two vertices x and y in H with the same distance to v and thus rm(x|RH ) = rm(y|RH). Let NH(v) = {v1, v2, · · · , vdeg(v)}. If there exists a vertex vi in NH(v… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Multiset Dimension of Graphs: Extremal Values and King Grids

    math.CO 2026-07 accept novelty 8.0 of 10

    Multiset dimension attains the trivial upper bound n(G) for the first time at order 11 (eight graphs), equals 4 on every n×n king grid n ≥ 5, and equals n on every 3×n king strip n ≥ 6.

  2. Multiset resolvability parameters in graphs: A survey with new results and open problems

    math.CO 2026-07 accept novelty 5.0 of 10

    Multiset resolvability parameters are surveyed; sharp outer-multiset lower bounds for diameter-two and join graphs are proved, and block graphs with local multiset dimension two are characterized.

  3. A Survey on Multiset Dimension and Its Variations

    math.CO 2026-07 conditional novelty 2.5 of 10

    A literature survey consolidates results on multiset dimension and its local/outer/edge variants and proposes new multiset partition and related parameters as open directions.

Reference graph

Works this paper leans on

5 extracted references · 4 canonical work pages · cited by 3 Pith papers

  1. [4]

    Simanjuntak, P

    R. Simanjuntak, P. Siagian, and T. Vetrík, On the multise t dimension of a graph, arXiv:1711.00225

    arXiv

  2. [1]

    Harary and R

    F. Harary and R. A. Melter, On the metric dimension of a gra ph, Ars Combin., 2 (1976), 191-195

    work page 1976

  3. [2]

    Khemmani and S

    V. Khemmani and S. Isariyapalakul, The multiresolving s ets of graphs with prescribed multisimilar equivalence classes, Int. J. Math . Math. Sci., 2018 (2018), ID 8978193

    work page 2018

  4. [3]

    B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Computation, 60 (2013), 94–112

    work page 2013

  5. [5]

    P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 5 49-559

    work page 1975

Pith tools

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