Multiset Dimension of Cylindrical Graphs: An Infinite Family and a Certified Census
Multiset dimension asks how few landmarks distinguish every graph vertex when only the unordered multiset of landmark distances is observed. For the cylindrical graph P_m × C_(6m) and every even integer m ≥ 2, we prove that (0,0), (0,2m), and (m−1,0) form a multiset basis; consequently, dim_m(P_m × C_(6m)) = 3. The proof recovers labelled distance data from its multiset by parity and rules out the only possible label swap using a four-piece description of the relevant cycle-distance locus. This gives an exact infinite family. A separately implemented exhaustive checker also determines the maximum path order resolved by any three boundary-row landmarks for every cycle order 4 ≤ n ≤ 100 and gives the complete multiset-dimension table for 3 ≤ m ≤ 7 and 3 ≤ n ≤ 14. It closes 55 entries in the 4 ≤ n ≤ 14 subbox that were not previously exact, identifies exactly nine dimension-five cylinders, and improves six published five-landmark constructions to four landmarks. Explicit witnesses, exhaustive lower-bound searches, and strict-schema corruption tests accompany the classifications; the computation is independent of the proof of the infinite family.
Authors
- Lennart Rudolph (ORCID: https://orcid.org/0009-0009-0198-085X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-08-14
- DOI
- https://doi.org/10.5281/zenodo.21925458
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint