The Outer Multiset Dimension of Toroidal Grids
Abstract
Let S be a set of vertices in a connected graph G. A vertex outside S is represented by the multiset of its distances to the vertices of S. The outer multiset dimension odim(G) is the minimum cardinality of an S for which these representations distinguish all vertices outside S. We determine odim(Cs □ Ct) for all s,t≥ 3, answering a problem of Klavžar, Kuziak, and Yero. The values range from $3$ to $8$. The proof combines a half-turn argument giving a universal four-landmark lower bound when both factors have length at least four, explicit three- and four-landmark constructions for the infinite families, and exact finite enumeration on the remaining strip. The collision classification behind the infinite four-landmark construction is certified by exact quantifier elimination in linear integer arithmetic; source code and all finite upper certificates accompany the paper.
Related
- Zeros and interlacing for multiset Eulerian-Narayana polynomials
- On the Injectivity of Elementary Symmetric Partitions and the Multiset Recovery Problem
- A Romanoff-type theorem for a multiset of products of powers
- Multiset Colorings of Random Graphs Across Density Regimes
- Time-reliability optimization of multi-pass underfill dispensing sequences on printed circuit boards: a schedule-dependent reliability model solved by a multiset-permutation binary-addition-tree algorithm
BibTeX
@misc{peng2026outer,
title = {{The Outer Multiset Dimension of Toroidal Grids}},
author = {Bo Peng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20073},
eprint = {2609.20073},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20073},
}
RIS
TY - UNPB
TI - The Outer Multiset Dimension of Toroidal Grids
AU - Bo Peng
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20073
UR - https://arxiv.org/abs/2609.20073
AB - Let S be a set of vertices in a connected graph G. A vertex outside S is represented by the multiset of its distances to the vertices of S. The outer multiset dimension odim(G) is the minimum cardinality of an S for which these representations distinguish all vertices outside S. We determine odim(C_s □ C_t) for all s,t≥ 3, answering a problem of Klavžar, Kuziak, and Yero. The values range from $3$ to $8$. The proof combines a half-turn argument giving a universal four-landmark lower bound when both factors have length at least four, explicit three- and four-landmark constructions for the infinite families, and exact finite enumeration on the remaining strip. The collision classification behind the infinite four-landmark construction is certified by exact quantifier elimination in linear integer arithmetic; source code and all finite upper certificates accompany the paper.
ER -