Local (Outer) Multiset Dimensions of Graphs

M. Ali Hasan; Muhung Anggarawan; Rinovia Simanjuntak

REVIEW 3 major objections 4 minor 2 cited by

Local (Outer) Multiset Dimensions of Graphs

T0 review · 3 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 This paper introduces the local outer multiset dimension and establishes sharp lower bounds and exact values for cycles, wheels, and clique-based constructions.

desk verdict New parameter with plausible lower bounds, but the wheel theorem is false and the sharpness construction for the clique bound does not work. read the letter →

arxiv 2507.15071 v1 pith:PKXX3A2W submitted 2025-07-20 math.CO

Rinovia Simanjuntak , M. Ali Hasan , Muhung Anggarawan This is my paper · ORCID

classification math.CO MSC 05C12

keywords localmultisetdimensionouterresolvingsetdistance-basedgraphinvariantwheelscyclescliquelowerbound

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

Fix a set $W$ of landmarks in a graph. A vertex's representation multiset $m(u|W)$ lists, with multiplicity, the distances from $u$ to the landmarks. The paper studies two ways of using these multisets to tell adjacent vertices apart: the local multiset dimension requires every edge's endpoints to have different multisets, while the new local outer multiset dimension only checks endpoints outside $W$ and therefore exists finitely for every graph. The main results are sharp lower bounds: both dimensions are at least $\lceil \log_2 \omega(G)\rceil$, where $\omega(G)$ is the largest clique size, and at least a binomial function of the diameter and chromatic number. Exact values are then computed for cycles, wheels, amalgamations of complete graphs, and corona products. A sympathetic reader takes away that distance multisets are a compact, universally available way to certify that each edge is locally identifiable.

What carries the argument

The machinery has three parts. The first is the representation multiset itself: for a landmark set $W$, each vertex $u$ carries $m(u|W)$, the multiset of distances to $W$. The second is the K-end vertex condition: inside a clique $K_r$, a vertex of degree $r-1$ cannot share membership status with another such vertex, forcing all but one of them into every resolving set; this yields the amalgamation and corona formulas. The third is a counting argument: in a diameter-$d$ graph with $k$ landmarks, the number of possible representation multisets is bounded by a binomial expression, which produces the chromatic-number bound and, specialized to a clique of size $n$, gives $\lceil \log_2 n \rceil$. The sharpness construction attaches paths of doubling lengths to clique vertices and labels extra clique vertices with binary patterns, so that each clique vertex gets a distinct multiset. For wheels, a path-restriction lemma trims the possible selected and unselected runs of rim vertices.

What would settle it

Check the wheel $W_6$ with landmark set $W=\{1,2,6\}$ on the rim: one computes $m(1|W)=\{0,1,1\}$ and $m(2|W)=\{0,1,2\}$, so two adjacent selected rim vertices have distinct multisets even though $W$ distinguishes all adjacent pairs. That directly contradicts Lemma 1, the premise used to exclude smaller sets in the wheel proof.

Watch

Extended reading notes

Core claim

The central discovery is that the local (outer) multiset dimension is governed by clique size and by the pair (diameter, chromatic number). The paper proves $\mathrm{lmd}(G) \ge \lceil \log_2 \omega(G) \rceil$ and $\mathrm{ldimms}(G) \ge \lceil \log_2 \omega(G) \rceil$, and constructs, for every $n$, a graph with $\omega(G)=n$ in which both dimensions equal $\lceil \log_2 n \rceil$. It also proves a counting lower bound $g(d,\chi(G))$ from the number of possible distance multisets in a graph of diameter $d$ and chromatic number $\chi(G)$. On the exact-value side, it shows even cycles have dimension 1, odd cycles have local multiset dimension 3 for $n\ge 7$ or infinity for $n=3,5$, and wheels have dimension $\lceil n/4\rceil$ in the even cases, with the local outer dimension one larger for certain odd wheels and infinite local multiset dimension for other odd wheels. For clique amalgamations and coronas, formulas are expressed through K-end vertices, vertices of a clique whose only incident edges are the clique edges.

Load-bearing premise

The wheel formulas rest on the lemma that two adjacent rim vertices both inside the landmark set, or both outside it, always have equal representation multisets; if that equality fails, the exact wheel dimensions lose the argument that rules out smaller candidate sets.

Editorial extensions

If this is right

If the $\lceil \log_2 \omega(G)\rceil$ bound is correct, graphs with a large clique require logarithmically many landmarks, and the paper's construction shows the bound is tight.
Since every graph has a finite local outer multiset dimension, the local outer parameter never suffers the infinitude that plagues the local multiset dimension on diameter-two graphs.
For cycles, the local outer dimension is 1 when $n$ is even and 2 when $n$ is odd, matching the bipartite characterization and giving a clean parity rule.
For wheels, the exact formulas show a parity-driven phase transition: many odd wheels have infinite local multiset dimension while their local outer dimension remains finite.
Complete graphs satisfy $\mathrm{ldimms}(K_n)=n-1$ for $n\ge 2$, so the new parameter inherits the extremal behavior of the outer multiset dimension on cliques.

Reading between the lines

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

Our inference: the doubling-path construction behind Theorem 11 may generalize to other local distinguishing parameters, such as edge versions, because only the clique's internal distances and the pendant path lengths matter.
Our inference: the paper leaves graph joins open; since every join has diameter at most 2, the binomial bound $g(2,\chi)$ gives a concrete starting estimate for $\mathrm{lmd}(G+H)$ and $\mathrm{ldimms}(G+H)$.
Our inference: because the local outer dimension is always finite, it could serve as a universal local distinguishing number for all finite connected graphs; a testable question is whether the gap between $\mathrm{ldimms}(G)$ and $\mathrm{lmd}(G)$ can be made arbitrarily large.
Our inference: the wheel proof's path-length restrictions suggest that similar parity constraints may control other graphs built from a center joined to a cycle, such as fans and gears.

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.

Desk Editor's Note

read the letter

Short version: the paper defines a natural new parameter and has some plausible counting lower bounds, but the wheel theorem is flat wrong and the sharpness construction for the clique-number bound has a hole. I would not trust the results as they stand.

What's actually new and good: The local outer multiset dimension (ldimms) is a reasonable addition to the metric-dimension zoo, and the observation that every graph has finite ldimms is correct. The lower bound ldimms(G) ≥ ⌈log2 ω(G)⌉ (first part of Theorem 11) is a solid pigeonhole argument and may be right. The chromatic-number-based bound in Theorem 12 also looks plausible, though I can't vouch for the sharpness beyond bipartite graphs. The paper is clearly written and engages with the existing literature.

The soft spots are serious. Lemma 1 is false. The claim that two adjacent rim vertices in a local multiset resolving set for a wheel must have the same representation is contradicted by W6: take W={1,2,6} on the rim. Vertices 1 and 2 are adjacent and both in W, yet m(1|W)={0,1,1} and m(2|W)={0,1,2}. This isn't a small typo; the lemma is load-bearing for Theorem 15. Worse, Theorem 15's value for W6 is simply wrong: W={1,5} is a 2-element local multiset resolving set and local outer resolving set, so lmd(W6)=ldimms(W6)=2, not 3. I checked all seven edges; the multisets are distinct, and no singleton can work because the graph contains a triangle. So the wheel table is incorrect.

The sharpness construction in Theorem 11 also fails. For n=2^k, the vertices v_i with i>k all get the same all-odd distance vector to W, so distinct clique vertices end up with identical representation multisets. The special labels for v0 and v_{2^k-k-1} don't fix that. Theorem 8's proof has a gap for the ldimms=1 converse, and Theorem 9's formulas mix up n and the cycle length.

Who is this for? Someone working on metric-dimension variants might want the definition and the lower bounds, but they should not rely on the wheels or the sharpness example. I'd recommend a major revision and a fresh check of all the constructions, not acceptance in the current form.

Recommendation: reject in current form, but the definition and some of the counting arguments are worth salvaging. A referee could usefully point to the wheel counterexample.

Referee Report

3 major / 4 minor

Summary. The paper defines the local multiset dimension (lmd) and local outer multiset dimension (ldimms) of a graph, in which adjacent vertices (or adjacent vertices outside the resolving set) must have distinct distance multisets to a chosen vertex set. It derives inequalities relating these parameters to previously studied dimensions, gives lower bounds in terms of clique number, chromatic number and diameter, computes exact values for vertex/edge amalgamations of cliques, corona products, non-cycle unicyclic graphs, cycles, and wheels, and poses open problems about graph joins and sharp upper bounds.

Significance. The definitions and the basic inequality chain in Observation 1 are natural and clearly presented, and the paper is fully self-contained in the sense that it contains no fitted parameters or empirical claims. If the main theorems were correct, the bounds in Theorems 11--13 and the wheel computations would be useful contributions to the local multiset dimension literature. However, the two central constructive results---Theorem 11 and Theorem 15---rest on false statements, and the wheel values are directly contradicted by a small example. Because the load-bearing claims fail, the paper in its current form does not establish its main results.

major comments (3)

[Theorem 11] Lemma 1(1) is false. In W6, the set W={1,2,6} of rim vertices is a valid local multiset resolving set: the representations are m(1|W)={0,1,1}, m(2|W)={0,1,2}, m(3|W)={1,2,2}, m(4|W)={2,2,2}, m(5|W)={1,2,2}, m(6|W)={1,2,0}, and m(vp|W)={1,1,1}, so every adjacent pair is distinguished. Yet W'_6[W] contains the path 2-1-6, contradicting the 'P2' assertion. Since Theorem 15 depends directly on Lemma 1, the wheel formulas collapse. In fact, in W6 the set W={1,5} has size 2 and gives m(1)={0,2}, m(2)={1,2}, m(3)={2,2}, m(4)={1,2}, m(5)={2,0}, m(6)={1,2}, m(vp)={1,1}, which distinguishes every adjacent pair; because W6 contains a triangle, no singleton resolves it, so lmd(W6)=2 and likewise ldimms(W6)=2. This directly contradicts the '3, if n=4,6' entries in Theorem 15.
[Theorem 9] The sharpness construction in Theorem 11, Case 1, does not produce a local multiset resolving set. For each i=1,...,k, the vertex v_i is labelled with ai,i=2i and ai,j=2j+1 for j≠i, so m(v_i|W)={2i}∪{2j+1:j≠i}. The clique vertex u_i has the identical multiset, because d(u_i,u_i,2i)=2i and d(u_i,u_j,2j)=2j+1 for j≠i. Since v_i and u_i are adjacent, W fails. For example, when k=3 both u1 and v1 have representation {2,5,7}. Thus the claim that ldimms(G)=lmd(G)=⌈log2 n⌉ is attained is not established.
[Minor comments] The proof of Theorem 9 contains incorrect distance formulas. The symbol n is used both for the order of G and for the length of the odd cycle, and the entry for k+3≤i≤n is wrong. In C5 (k=2), the vertex c4 satisfies m(c4|{t1,c2})={2,3}, whereas the printed formula {n-i+2,n-i+2} gives {3,3}. The proof therefore does not demonstrate that all adjacent cycle vertices have distinct representation multisets as written.

minor comments (4)

[Theorem 15] The spelling 'Corrolary' should be 'Corollary', and 'unicylic' should be 'unicyclic'.
[Theorem 11] In the last paragraph of the proof, the expressions 'lmd(Wm)=⌈m/4⌉+1' should refer to ldimms(Wn), with n rather than m, and the final sentence should say ldimms rather than lmd.
[Theorem 8] In the proof of Theorem 11, the sentence stating that the entries of m(vi|W) are 'all even except for one' is reversed: each vi has exactly one even entry and the remaining entries are odd.
[Theorem 8] The opening sentence of Section 3 promises a characterization of graphs with the local (outer) multiset dimensions equal to 1, but Theorem 8 as stated only characterizes the conjunction lmd(G)=ldimms(G)=1. If the authors intend the separate statement 'ldimms(G)=1 if and only if G is bipartite', an additional proof is needed, since ldimms≤lmd alone does not rule out ldimms=1 when lmd>1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs are explicit constructions or counting arguments, and the only self-citation is background material, not load-bearing.

full rationale

The paper's central results (Theorems 5–7, 9, 11, 12, and 15) are derived from the definitions of local (outer) multiset resolving sets via explicit vertex-set constructions, distance-multiset computations, and counting arguments. No parameter is fitted to data and no 'prediction' is made from a fitted quantity. The lower bounds in Theorems 11 and 12 are proved by counting possible representation multisets, and the sharpness constructions are explicit labeled graphs with resolving sets W exhibited and verified by multiset calculations, so the conclusions do not reduce to the assumptions by construction. The wheel argument in Section 4 invokes Theorem 14 from Reference [8] (external authors) as a lower bound. The only citation to the present first author's prior work, Reference [4], supplies background results on the non-local multiset dimension (e.g., Theorem 1 and the value md(Cn)=3); those results are independently published and are not the load-bearing source of the new wheel or sharpness claims. The skeptical review's concern that Lemma 1 and Theorem 15 may be mathematically false is a correctness issue, not a circularity issue: a false lemma would invalidate the proof but does not make the derivation a disguised restatement of its inputs. No self-definitional reduction, fitted-input prediction, or uniqueness-imported-by-self-citation occurs.

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

The central claims rest only on standard graph theory definitions and counting; no free parameters or invented entities. The main fragility is in the proof arguments, not in hidden assumptions.

assumptions (1)

domain assumption Graphs are finite, connected, undirected, and simple
Stated at the start of Section 1 and used throughout the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Local (Outer) Multiset Dimensions of Graphs." pith.science (2026). https://pith.science/paper/PKXX3A2W

@misc{pith2026250715071,
  author       = {Pith},
  title        = {Pith review of: Local (Outer) Multiset Dimensions of Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PKXX3A2W}},
  note         = {Machine review of arXiv:2507.15071}
}

abstract

Let $G$ be a finite, connected, undirected, and simple graph and $W$ be a set of vertices in $G$. A representation multiset of a vertex $u$ in $V(G)$ with respect to $W$ is defined as the multiset of distances between $u$ and the vertices in $W$. If every two adjacent vertices in $V(G)$ have a distinct multiset representation, the set $W$ is called a local multiset resolving set of $G$. If $G$ has a local multiset resolving set, then this set with the smallest cardinality is called the local multiset basis, and its cardinality is the local multiset dimension of $G$. Otherwise, $G$ is said to have an infinite local multiset dimension. On the other hand, if every two adjacent vertices in $V(G) \backslash W$ have a distinct representation multiset, the set $W$ is called a local outer multiset resolving set of $G$. Such a set with the smallest cardinality is called the local outer multiset basis, and its cardinality is the local outer multiset dimension of $G$. Unlike the local multiset dimension, every graph has a finite local outer multiset dimension. This paper presents some basic properties of local (outer) multiset dimensions, including lower bounds for the dimensions and a necessary condition for a finite local multiset dimension. We also determine local (outer) multiset dimensions for some graphs of small diameter.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

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

9 extracted references · 7 canonical work pages · cited by 2 Pith papers

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION string.to.integer 't := t text.length 'k := #1 'char.num := t char.num #1 substring 's := s is.num s "." = or char.num k = not and char.num #1 + 'char.num := while char.num #1 - 'char.num := t #1 char.num substring FUNCTION find.integer 't := #0 'int := int not t empty not and t #1 #1 substring 's :=...
[2]

, Melter , R.A

barticle Harary , F. , Melter , R.A. : Leaves of trees . Congress. Numer. 14 , 549 -- 559 ( 1975 ) barticle

work page 1975
[3]

, Melter , R.A

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

work page 1976
[4]

, Phinezy , B

barticle Okamoto , F. , Phinezy , B. , Zhang , P. : The local metric dimension of a graph . Math. Bohemica 135 ( 3 ), 239 -- 255 ( 2010 ) barticle

work page 2010
[5]

, Vetrik , T

botherref Simanjuntak , R. , Vetrik , T. , Mulia , P.B. : The multiset dimension of graphs. arXiv 1711.00225 (2017) botherref

arXiv 2017
[6]

, Ramírez-Cruz , Y

barticle Gil-Pons , R. , Ramírez-Cruz , Y. , Trujillo-Rasua , R. , Yero , I.G. : Distance-based vertex identification in graphs: The outer multiset dimension . App. Math. Comput. 363 , 124612 ( 2019 ) barticle

work page 2019
[7]

, Kuziak , D

barticle Klavzar , S. , Kuziak , D. , Yero , I.G. : Further contributions on the outer multiset dimension of graphs . Results in Math. 78 , 50 ( 2023 ) barticle

work page 2023
[8]

, Dafik , Kristiana , A.I

barticle Alfarisi , R. , Dafik , Kristiana , A.I. , Agustin , I.H. : The local multiset dimension of graphs . Int. J. Eng. Tech. 8 ( 3 ), 120 -- 124 ( 2019 ) barticle

work page 2019

Show all 9 references

[9]

, Cynthia , V.J.A

barticle Fancy , V.F. , Cynthia , V.J.A. : Local metric dimension of certain wheel related graphs . Inter. J. Math. Comp. Sci. 16 ( 4 ), 1303 -- 1315 ( 2021 ) barticle

2021

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION string.to.integer 't := t text.length 'k := #1 'char.num := t char.num #1 substring 's := s is.num s "." = or char.num k = not and char.num #1 + 'char.num := while char.num #1 - 'char.num := t #1 char.num substring FUNCTION find.integer 't := #0 'int := int not t empty not and t #1 #1 substring 's :=...

[2] [2]

, Melter , R.A

barticle Harary , F. , Melter , R.A. : Leaves of trees . Congress. Numer. 14 , 549 -- 559 ( 1975 ) barticle

work page 1975

[3] [3]

, Melter , R.A

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

work page 1976

[4] [4]

, Phinezy , B

barticle Okamoto , F. , Phinezy , B. , Zhang , P. : The local metric dimension of a graph . Math. Bohemica 135 ( 3 ), 239 -- 255 ( 2010 ) barticle

work page 2010

[5] [5]

, Vetrik , T

botherref Simanjuntak , R. , Vetrik , T. , Mulia , P.B. : The multiset dimension of graphs. arXiv 1711.00225 (2017) botherref

arXiv 2017

[6] [6]

, Ramírez-Cruz , Y

barticle Gil-Pons , R. , Ramírez-Cruz , Y. , Trujillo-Rasua , R. , Yero , I.G. : Distance-based vertex identification in graphs: The outer multiset dimension . App. Math. Comput. 363 , 124612 ( 2019 ) barticle

work page 2019

[7] [7]

, Kuziak , D

barticle Klavzar , S. , Kuziak , D. , Yero , I.G. : Further contributions on the outer multiset dimension of graphs . Results in Math. 78 , 50 ( 2023 ) barticle

work page 2023

[8] [8]

, Dafik , Kristiana , A.I

barticle Alfarisi , R. , Dafik , Kristiana , A.I. , Agustin , I.H. : The local multiset dimension of graphs . Int. J. Eng. Tech. 8 ( 3 ), 120 -- 124 ( 2019 ) barticle

work page 2019