{"id":"e6dea48d-d4e8-4af4-920e-6e707f11710b","arxiv_id":"2607.10311","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This survey collects multiset-based variants of metric dimension in graphs and proves new sharp lower bounds plus a characterization of block graphs with local multiset dimension two. It organizes a growing literature and lists open problems for future work.","discovery_kind":"review","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript’s central new claims—the sharp lower bounds of Theorems 4.12 and 4.13 that solve two open problems, and the clean characterization of block graphs with local multiset dimension two—are elementary, fully written, and free of gaps. The only potential soft spot flagged by the reader is illusory: diameter two forces every multiset to be of the form {1^a,2^{|S|-a}}, so the counting argument is exhaustive by definition. The remainder of the paper is a competent survey that correctly compiles known results and open questions. No circularity, free parameters, or unverifiable computer claims affect the analytic core. Consequently the reader’s ACCEPT verdict with high confidence requires no adjustment.","tokens_in":26921,"tokens_out":469,"duration_ms":4217,"concrete_test":"Independently re-derive the counting step of Theorem 4.12: list all possible distance multisets that a vertex outside S can realize when diam(G)=2; confirm that only the Δ+1 patterns {1^a,2^{|S|-a}} appear and that the two cases |S|≤n-Δ-2 and |S|=n-Δ-1 each produce a collision or a missing common neighbor. If the enumeration remains complete, the bound stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption worry (that Theorems 4.12–4.13 might miss exotic multiset patterns under diam=2) does not land. In a diameter-two graph every distance is 1 or 2, so for any S and any v outside S the multiset m(v|S) is completely determined by the single integer a = |N(v)∩S|; it is always of the form {1^a,2^{|S|-a}} with 0≤a≤Δ. There are therefore exactly Δ+1 possible distinct multisets, and the case analysis that forces |S|≥n-Δ (and the analogous counting for joins) is exhaustive. The same elementary distance restriction underpins the sharpness constructions and the block-graph characterization (Theorem 5.21). No hidden assumption or incomplete enumeration is present.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.5","summary":"The manuscript surveys multiset-based resolvability parameters (multiset dimension, outer multiset dimension, local multiset dimension, edge multiset dimension, and k-multiset antidimension), collecting known results, complexity statements, and product formulae. It contributes three new theorems: a sharp lower bound dim_om(G) ≥ n(G)-Δ(G) for every diameter-two graph (Theorem 4.12), the related bound dim_om(G+K_m) ≥ n(G)-Δ(G)+m-2 (Theorem 4.13), both solving open problems from the literature, and a characterization of block graphs with local multiset dimension exactly two as the family B of clique-number-3 block graphs that admit a shortest even path meeting every triangle in exactly two vertices (Theorem 5.21). The paper closes with a compiled list of open problems, some new.","tokens_in":27041,"tokens_out":783,"duration_ms":6219,"significance":"The survey organizes a scattered literature that has grown rapidly since the independent rediscoveries of multiset dimension. The two new outer-multiset lower bounds are short, self-contained combinatorial arguments that settle concrete open questions (Problems 6.1 of [35] and Problems 2–3 of [47]) and are shown to be sharp by explicit constructions. The block-graph characterization is the first structural description of graphs with local multiset dimension two beyond the bipartite case. The open-problem list is carefully curated and will be useful for subsequent work. No machine-checked proofs or code are supplied, but the combinatorial arguments are elementary and fully explicit.","major_comments":[],"minor_comments":[{"comment":"In the proof of Theorem 4.12 the phrase “the set {u1,…,uk} is as an outer multiset resolving set” contains a superfluous “as”; likewise a few other minor grammatical slips appear (e.g., “mutiset” in §3.5).","section":null},{"comment":"Figure 1 caption and the surrounding text refer to an outer multiset basis of Q3 of size 5, yet the figure itself is not fully self-explanatory; a short sentence listing the five black vertices would help the reader verify the claim.","section":null},{"comment":"Tables 1–2 report computer-search values for subdivision graphs K_n^k; a one-sentence description of the enumeration method (or a reference to the nauty catalogue already cited later) would make the computational claims more transparent.","section":null},{"comment":"The definition of the family F of graphs with outer multiset dimension 2 (just before Theorem 4.6) is a little dense; a short clarifying remark that the optional edges are precisely those that preserve the multiset distinction would improve readability.","section":null},{"comment":"In §6.1 the authors correctly retract the incorrect examples of [29] that claimed dim_m \neq edim_m; it would be helpful to state explicitly that the three inequalities are nevertheless realized by the new examples of Figures 5–6.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a solid survey-plus-new-results paper that fits well in a combinatorial journal. The new theorems are short and correct; the only possible editorial concern is length, but the open-problem compilation justifies the space. No citation or novelty issues detected."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The two things worth knowing: Theorems 4.12 and 4.13 give sharp lower bounds dim_om(G) ≥ n-Δ for diameter-two graphs and the analogous bound for joins G+K_m, solving the open problems posed in [35] and [47]; Theorem 5.21 completely characterizes the block graphs with local multiset dimension exactly 2. Both are short, self-contained combinatorial arguments that work.\n\nWhat is new is modest but real. The bulk of the manuscript is a careful survey that unifies results previously scattered under “multiset dimension” and “ID-coloring” terminology, plus the edge and k-antidimension variants. The new lower bounds rest on the elementary observation that, under diam=2, every multiset m(v|S) is completely determined by the single integer a=|N(v)∩S|, so there are at most Δ+1 possible signatures; the counting and the twin/common-neighbor contradictions are exhaustive. The sharpness constructions (the family G_k and the generalized fans) are explicit. The block-graph characterization is likewise clean: a block graph has dim_lm=2 precisely when it has clique number 3 and admits a shortest even path that hits every triangle in exactly two vertices. Computer tables for hypercubes and subdivision graphs are given without code, but the analytic claims stand independently.\n\nSoft spots are minor. The survey sections are thorough rather than deep; a few earlier claims in the edge-multiset literature are corrected by brute-force checks, which is honest. No circularity, free parameters, or hidden assumptions appear. The open-problem list at the end is useful and includes several new questions that look worth pursuing.\n\nThis is for people already working on metric dimension variants or who need a single reference for the multiset versions. It is not transformative, but it is competent, correctly proved, and solves the problems it claims to solve. I would send it to referees without hesitation; the new theorems are short enough that verification is straightforward and the survey value is clear.","headline":"Solid survey-plus-results paper that cleanly settles two open problems on outer multiset dimension and gives a clean characterization for block graphs; the new math is elementary and correct, the rest is useful organization of a scattered literature.","tokens_in":27689,"tokens_out":519,"would_cite":true,"duration_ms":5956,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12"],"pacs":[],"model":"grok-4.5","headline":"Multiset distance codes give new sharp lower bounds on outer multiset dimension and a clean characterisation of block graphs of local multiset dimension two.","keywords":["multiset dimension","outer multiset dimension","local multiset dimension","edge multiset dimension","k-multiset antidimension","metric dimension","block graphs","diameter-two graphs"],"falsifier":"Exhibit a diameter-two graph whose outer multiset dimension is strictly smaller than n-Δ, or a block graph outside family B that nevertheless has local multiset dimension two.","tokens_in":27811,"feed_emoji":"📐","tokens_out":847,"duration_ms":7440,"temperature":0.7,"pith_summary":"This survey collects everything known about graph resolvability that uses multisets of distances rather than ordered vectors. The multiset versions model anonymous sensors or landmarks whose identities are unknown; only the collection of distances matters. Along the way the authors prove two sharp lower bounds that settle open questions: every diameter-two graph needs at least n-Δ vertices in any outer multiset resolving set, and the same idea yields a matching bound for joins with empty graphs. They also characterise exactly which block graphs have local multiset dimension two—they are the graphs of clique number three that admit an even-length shortest path hitting every triangle in precisely two vertices. The paper ends with a consolidated list of open problems that maps the remaining terrain.","feed_headline":"Sharp multiset bounds settle open problems on diameter-two graphs","feed_subtitle":"Outer multiset dimension is at least n-Δ; block graphs of local dimension two are fully classified.","key_machinery":"Outer multiset resolving sets (and their local counterparts): a set S whose multiset of distances distinguishes every vertex outside S (respectively, every pair of adjacent vertices). The new lower bounds rest on exhaustive enumeration of the possible multiplicity patterns of distance-1 entries inside those multisets under the diameter-two hypothesis.","core_discovery":"For every graph G of diameter two the outer multiset dimension satisfies dim_om(G) ≥ n(G)-Δ(G), and the bound is attained by an infinite family of graphs of order 2k+1. The same counting argument yields the sharp lower bound dim_om(G+K_m) ≥ n(G)-Δ(G)+m-2. Independently, a block graph has local multiset dimension exactly two if and only if it belongs to the explicitly defined family B of clique-number-three block graphs that contain a shortest even path meeting every triangle in exactly two vertices.","pith_inferences":["The multiset model is a genuine worst-case analogue of classical metric dimension for anonymous sensors; algorithms that ignore landmark identity can now be bounded against the new outer-multiset lower bounds.","The block-graph characterisation suggests that local multiset dimension is governed by the parity of paths through odd cliques; a similar parity obstruction may control the parameter on all chordal graphs.","Because the same multiset codes appear in both the resolvability and the antiresolvability (privacy) settings, the new diameter-two bounds may translate into concrete anonymity guarantees for social graphs of small diameter."],"forward_implications":["Any future exact formula for outer multiset dimension of diameter-two graphs must respect the n-Δ lower bound.","Join constructions G+K_m inherit a simple closed-form lower bound that is already tight for fans and generalised fans.","Local multiset dimension two is completely settled for the class of block graphs; the same structural description may extend to other chordal or tree-like families.","The consolidated open-problem list supplies concrete targets (hypercubes, random graphs, Cartesian products of cycles) for the next wave of research."],"fun_headline_variants":["Outer multiset dim ≥ n-Δ for diameter-two graphs, bound sharp","New bounds settle open outer multiset problems on diam-2 and joins","Block graphs of local multiset dim two fully classified","Multiset resolvability survey yields sharp diam-2 bounds and open problems","Local multiset dim two characterized for block graphs of clique number three"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The counting arguments treat the list of possible distance-1 multiplicities under diameter two as exhaustive; if an exotic multiset pattern not captured by that list can arise, the lower-bound proofs fail.","fun_headline_variants_meta":{"raw":{"variants":["Outer multiset dim ≥ n-Δ for diameter-two graphs, bound sharp","New bounds settle open outer multiset problems on diam-2 and joins","Block graphs of local multiset dim two fully classified","Multiset resolvability survey yields sharp diam-2 bounds and open problems","Local multiset dim two characterized for block graphs of clique number three"]},"model":"grok-4.5","effort":"low","cost_usd":0.003652,"raw_usage":{"total_tokens":1150,"prompt_tokens":764,"num_sources_used":0,"completion_tokens":96,"cost_in_usd_ticks":36520000,"prompt_tokens_details":{"text_tokens":764,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":290,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":764,"tokens_out":96,"duration_ms":4128,"temperature":1.0,"reasoning_tokens":290,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T12:42:40.287576+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a diameter-two graph whose outer multiset dimension is strictly smaller than n-Δ, or a block graph outside family B that nevertheless has local multiset dimension two.","supporting_citations":[],"review_version":1}