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

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 the vertices (0,0), (0,2m), and (m − 1,0) form a multiset basis of P_m □ C_(6m); consequently, dim_m(P_m □ C_(6m)) = 3. The proof recovers the labelled distance data from its multiset by parity and then rules out the only possible label swap using a four-piece description of the relevant cycle-distance locus. This gives an exact infinite family. Complementing it, a separately implemented exhaustive checker 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 all 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.