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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Multiset Dimension of Cylindrical Graphs: An Infinite Family and a Certified Census

Lennart Rudolph
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Multiset Dimension of Cylindrical Graphs: An Infinite Family and a Certified Census

Lennart Rudolph
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Peace, Justice and strong institutions
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.