REVIEW 5 minor 1 cited by
Multiset resolvability parameters in graphs: A survey with new results and open problems
T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5
Pith's one-line read Multiset distance codes give new sharp lower bounds on outer multiset dimension and a clean characterisation of block graphs of local multiset dimension two.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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.
minor comments (5)
- 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).
- 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.
- 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.
- 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.
- In §6.1 the authors correctly retract the incorrect examples of [29] that claimed dim_m eq edim_m; it would be helpful to state explicitly that the three inequalities are nevertheless realized by the new examples of Figures 5–6.
Circularity Check
No significant circularity: new lower bounds and block-graph characterization are self-contained combinatorial arguments.
full rationale
The paper is a survey that also proves three new combinatorial results (Theorems 4.12, 4.13 and 5.21). Each proof proceeds by elementary counting or structural case analysis that never reduces to a fitted parameter, a self-citation uniqueness theorem, or a definition that already encodes the claimed inequality. In diameter-two graphs every multiset m(v|S) is forced to be of the form {1^a,2^{|S|-a}} with 0≤a≤Δ, so the Δ+1-pattern enumeration used in Theorems 4.12–4.13 is exhaustive by the definition of diameter, not by circular assumption. The block-graph characterization (Theorem 5.21) likewise rests only on uniqueness of shortest paths and the already-proved fact that dim_lm=1 precisely for bipartite graphs. Surveyed earlier results are properly attributed; self-citations merely introduce the parameters under discussion and do not underwrite the new claims. Consequently the derivation chain contains no circular step.
Assumptions & free parameters
assumptions (3)
- standard math Standard shortest-path distance in a finite connected undirected graph is a metric.
- domain assumption Definitions of multiset dimension, outer multiset dimension, local multiset dimension, edge multiset dimension and k-multiset antidimension as given in the cited source papers.
- standard math In a diameter-two graph the only possible distances appearing in any multiset representation are 1 and 2.
Cite this review
Pith. "Pith review of Multiset resolvability parameters in graphs: A survey with new results and open problems." pith.science (2026). https://pith.science/paper/CBUSVNR4
@misc{pith2026260710311,
author = {Pith},
title = {Pith review of: Multiset resolvability parameters in graphs: A survey with new results and open problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/CBUSVNR4}},
note = {Machine review of arXiv:2607.10311}
}
abstract
The metric dimension, which has lots of variants and numerous applications in other fields, is one of the most important and most extensively studied topics in metric graph theory. Results in which resolvability is achieved by considering multisets of distances from a fixed vertex, instead of vectors as in the original version, are surveyed. The concepts discussed are multiset dimension, outer multiset dimension, local multiset dimension, edge multiset dimension, and $k$-multiset antidimension. Along the way, sharp lower bounds on the outer multiset dimension of diameter two graphs and join graphs with edgeless graphs are proved, which solves two open problems from the literature. New results on graphs with local multiset dimension equal to two are also proved. In particular, such graphs are characterized among block graphs. Finally, a list of open problems from the literature is compiled, and several new problems are added to the list for future research.
Figures
Figures from the paper (4 more)
Forward citations
Cited by 1 Pith paper
-
The Multiset Dimension of Graphs: Extremal Values and King Grids
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.
Reference graph
Works this paper leans on
-
[35]
Klavˇ zar, D
S. Klavˇ zar, D. Kuziak, I.G. Yero, Further contributions on the outer multiset dimension of graphs, Result. Math. 78 (2023) Paper 50
2023
-
[47]
Pervaiz, R
H. Pervaiz, R. Simanjuntak, S.W. Saputro, Outer multiset dimension of joined graphs, Indonesian J. Combin. 9 (2025) 61–68
2025
-
[1]
Adawiyah, Dafik, R.M
R. Adawiyah, Dafik, R.M. Prihandini, E.R. Albirri, I.H. Agustin, R. Alfarisi, The local multiset dimension of unicyclic graph, IOP Conf. Series: Earth Environ. Sci. 243 (2019) Paper 012075
2019
-
[2]
Alfarisi, Dafik, A.I
R. Alfarisi, Dafik, A.I. Kristiana, I.H. Agustin, The local multiset dimension of graphs, Int. J. Eng. Tech. 8 (2019) 120–124. 27
2019
-
[3]
Alfarisi, Y
R. Alfarisi, Y. Lin, J. Ryan, Dafik, I.H. Agustin, A note on multiset dimension and local multiset dimension of graphs, Stat. Optim. Inf. Comput. 8 (2020) 890–901
2020
-
[4]
Alfarisi, L
R. Alfarisi, L. Susilowati, Dafik, O.J. Fadekemi, On the local multiset dimension of some families of graphs, WSEAS Trans. Math. 22 (2023) Paper 8
2023
-
[5]
Alfarisi, L
R. Alfarisi, L. Susilowati, Dafik, Local multiset dimension of comb product of tree graphs, AIMS Math. 8 (2023) 8349–8364
2023
-
[6]
Alfarisi, L
R. Alfarisi, L. Susilowati, Dafik, S. Prabhu, Local multiset dimension of amalgamation graphs, F1000Research 12 (2024) 95
2024
Show all 58 references
-
[7]
Alfarisi, L
R. Alfarisi, L. Susilowati, Dafik, A.I. Kristiana, Local multiset dimension of corona product on tree graphs, Discrete Math. Algorithms Appl. 16 (2024) Paper 2350092
2024
-
[8]
Alfarisi, L
R. Alfarisi, L. Susilowati, A.I. Kristiana, On the local multiset dimension of comb product graphs, Stat. Optim. Inf. Comput. 14 (2025) 1356–1361
2025
-
[9]
Ali, H.M.A
N. Ali, H.M.A. Siddiqui, M.I. Qureshi, S.A.O. Abdallah, A. Almahri, J. Asad, A. Akg¨ ul, Exploring ring structures: Multiset dimension analysis in compressed zero-divisor graphs, Symmetry (2024) Paper 930
2024
-
[10]
Ali, H.M.A
N. Ali, H.M.A. Siddiqui, M.I. Qureshi, M.E.M. Abdalla, N.S. Abd EL-Gawaad, F.T. Tolasa, On study of multiset dimension in fuzzy zero divisor graphs associated with commutative rings, Int. J. Comp. Intell. Systems 17 (2024) 298
2024
-
[11]
Ali, H.M.A
N. Ali, H.M.A. Siddiqui, M.I. Qureshi, On certain bounds for multiset dimensions of zero-divisor graphs associated with rings,arXiv:2405.06180[math.CO] (2024)
2024 arXiv
-
[12]
Ali, M.I
N. Ali, M.I. Qureshi, H.M.A. Siddiqui, ¨U. Karabiyik, T. Ayoubi, A. Smerat, Combinatorial study of multiset dimension and outer multiset dimension in V-graphs over rings, Research Math. 13 (2026) DOI:10.1080/27684830.2026.2638603
2026 doi
-
[13]
Behtoei, A
A. Behtoei, A. Davoodi, M. Jannesari, B. Omoomi, A characterization of some graphs with metric dimension two, Discrete Math. Algorithms Appl. 9 (2017) Paper 1750027
2017
-
[14]
Blumenthal, Theory and Applications of Distance Geometry
L.M. Blumenthal, Theory and Applications of Distance Geometry. Oxford University Press (1953)
1953
-
[15]
Bengeri, V
A. Bengeri, V. P.S, P. Poojary, S. Kumar Sharma, On multiset dimension of extended kayak paddle graph, Int. J. Comput. Math. Comput. Syst. Theory 10 (2025) 95–116
2025
-
[16]
N.H. Bong, Y. Lin, Some properties of the multiset dimension of graphs, Electron. J. Graph Theory Appl. 9 (2021) 215–221
2021
-
[17]
G. Cai, F. Xiao, G. Yu, The identification numbers of lollipop graphs, AIMS Math. 10 (2025) 7813– 7827
2025
-
[18]
C ¸ evik, Matching some graph dimensions with special presentations, Montes Taurus J
A.S. C ¸ evik, Matching some graph dimensions with special presentations, Montes Taurus J. Pure Appl. Math. 6 (2024) 78–89
2024
-
[19]
C ¸ evik, I.N
A.S. C ¸ evik, I.N. Cangul, Y. Shang, Matching some graph dimensions with special generating func- tions, AIMS Math. 10 (2025) 8446–8467. 28
2025
-
[20]
Chartrand, L
G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105(1-3) (2000) 99–113
2000
-
[21]
Chartrand, Y
G. Chartrand, Y. Kono, P. Zhang, Distance vertex identification in graphs, J. Interconnect. Netw. 21 (2021) Paper 2150005
2021
-
[22]
Cueno, A.D
A.L. Cueno, A.D. Garciano, R.M. Marcelo, Multiset dimension of Cayley digraphs of Abelian groups, J. Inf. Process. 33 (2025) 1056–1063
2025
-
[23]
A. Eide, P. Pra lat, Multiset metric dimension of binomial random graphs,arXiv:2507.11686 [math.CO] (2025)
2025 arXiv
-
[24]
Estrada-Moreno, E
A. Estrada-Moreno, E. Fern´ andez, D. Kuziak, M. Mu˜ noz-M´ arquez, R. Trujillo-Rasua, I.G. Yero, On the (k, ℓ)-multiset anonymity measure for social graphs,arXiv:2507.08433[math.CO] (2025)
2025 arXiv
-
[25]
Gil-Pons, Y
R. Gil-Pons, Y. Ram´ ırez-Cruz, R. Trujillo-Rasua, I.G. Yero, Distance-based vertex identification in graphs: the outer multiset dimension, Appl. Math. Comput. 363 (2019) Paper 124612
2019
-
[26]
Hafidh, R
Y. Hafidh, R. Kurniawan, S. Saputro, R. Simanjuntak; S. Tanujaya, S. Uttunggadewa, Multiset dimensions of trees,arXiv:1908.05879[math.CO] (2019)
1908 arXiv
-
[27]
Hakanen, I.G
A. Hakanen, I.G. Yero, Complexity and equivalency of multiset dimension and ID-colorings, Fundam. Inform. 191 (2024) 315–330
2024
-
[28]
Harary, R.A
F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195
1976
-
[29]
Ikhlaq, R
H.M. Ikhlaq, R. Ismail, H.M.A. Siddiqui, M.F. Nadeem, A new technique to uniquely identify the edges of a graph, Symmetry 15 (2023) Paper 762
2023
-
[30]
Isariyapalakul, V
S. Isariyapalakul, V. Khemmani, W. Pho-on, The multibases of symmetric caterpillars, J. Math. 2020 (2020) Paper 5210628
2020
-
[31]
Kelenc, A.T
A. Kelenc, A.T. Masa Toshi, R. ˇSkrekovski, I. G. Yero, On metric dimensions of hypercubes, Ars Math. Contemp. 23 (2023) Paper 8
2023
-
[32]
Kelenc, N
A. Kelenc, N. Tratnik, I.G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension. Discrete Appl. Math. 251 (2018) 204–220
2018
-
[33]
Khemmani, S
V. Khemmani, S. Isariyapalakul, The multiresolving sets of graphs with prescribed multisimilar equivalence classes, Int. J. Math. Math. Sci. 2018 (2018) Paper 8978193
2018
-
[34]
Khemmani, S
V. Khemmani, S. Isariyapalakul, The characterization of caterpillars with multidimension 3, Thai J. Math. 18 (2020) 247–259
2020
-
[36]
M. Knor, S. Majstorovi´ c, A.T. Masa Toshi, R. ˇSkrekovski, I.G. Yero, Graphs with the edge metric dimension smaller than the metric dimension, Appl. Math. Comput. 401 (2021) Paper 126076
2021
-
[37]
M. Knor, R. ˇSkrekovski, I.G. Yero, A note on the metric and edge metric dimensions of 2-connected graphs, Discrete Appl. Math. 319 (2022) 454–460. 29
2022
-
[38]
Y. Kono, P. Zhang, A note on the identification numbers of caterpillars, Discrete Math. Lett. 8 (2022) 10–15
2022
-
[39]
Y. Kono, P. Zhang, Vertex identification in grids and prisms, J. Interconnect. Netw. 22 (2022) Paper 2150019
2022
-
[40]
Y. Kono, P. Zhang, Vertex identification in trees, Discrete Math. Lett. 7 (2021) 66–73
2021
-
[41]
Kuziak, I.G
D. Kuziak, I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results,arXiv:2107.04877[math.CO] (2021)
2021 arXiv
-
[42]
Kumar Sharma, V.K
S. Kumar Sharma, V.K. Bhat, Independence in multiresolving sets of graphs, Int. J. Comput. Math. Comput. Syst. Theory 8 (2023) 99–107
2023
-
[43]
J.B. Liu, S. Kumar Sharma, V.K. Bhat, H. Raza, Multiset and mixed metric dimension for starphene and zigzag-edge coronoid,arXiv:2110.12368[math.CO] (2021)
2021 arXiv
-
[44]
Marcelo, M.A.C
R.M. Marcelo, M.A.C. Tolentino, A.D. Garciano, J.C. Buot, On multiset dimension of cylindrical graphs, J. Comb. Math. Comb. Comput. 126 (2025) 225–240
2025
-
[45]
McKay, A
B.D. McKay, A. Piperno, Practical graph isomorphism, II, J. Symb. Comput. 60 (2014) 94–112
2014
-
[46]
Okamoto, B
F. Okamoto, B. Phinezy, P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (2010) 239–255
2010
-
[48]
Riaz, H.M.A
A. Riaz, H.M.A. Siddiqui, N. Ali, Graph-theoretic characterization of rings: outer multiset dimension of zero-divisor graphs, Discrete Appl. Math. 377 (2025) 436–444
2025
-
[49]
Saenpholphat, On multiset dimension in graphs (in Thai), in: Proceedings of the 3rd Srinakhar- inwirot Academic Conference (2009) 193–202
V. Saenpholphat, On multiset dimension in graphs (in Thai), in: Proceedings of the 3rd Srinakhar- inwirot Academic Conference (2009) 193–202
2009
-
[50]
Samarati, L
P. Samarati, L. Sweeney, Protecting privacy when disclosing information:k-anonymity and its enforcement through generalization and suppression, Technical report, 1998.https:// dataprivacylab.org/dataprivacy/projects/kanonymity/paper3.pdf
1998
-
[51]
Shankar, S.B
N.R. Shankar, S.B. Chandrakala, B. Sooryanarayana, On the local multiset dimension of a graph, Discrete Math. Algorithms Appl. 18 (2025) Paper 2550018
2025
-
[52]
Simanjuntak, M
R. Simanjuntak, M. Ali Hasan, M. Anggarawan, Local (outer) multiset dimensions of graphs,arXiv: 2507.15071[math.CO] (2025)
2025 arXiv
-
[53]
Simanjuntak, T
R. Simanjuntak, T. Vetr´ ık, P. Bintang Mulia, The multiset dimension of graphs,arXiv:1711.00225 [math.CO] (2017)
2017 arXiv
-
[54]
Slater, Leaves of trees, Cong
P.J. Slater, Leaves of trees, Cong. Numer. 14 (1975) 549–559
1975
-
[55]
Tillquist, R.M
R.C. Tillquist, R.M. Frongillo, M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev. 65 (2023) 919–962
2023
-
[56]
Tillquist, M.E
R.C. Tillquist, M.E. Lladser, Low-dimensional representation of genomic sequences, J. Math. Biol. 79 (2019) 1–29. 30
2019
-
[57]
M. A. C. Tolentino, Identification number of antiprism graphs, Malays. J. Math. Sci. 19 (2025) 1553–1565
2025
-
[58]
Trujillo-Rasua, I
R. Trujillo-Rasua, I. G. Yero,k-metric antidimension: A privacy measure for social graph, Inf. Sci. 328 (2016) 403–417. 31
2016
Reviewed July 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.