The Multiset Dimension of Graphs: Extremal Values and King Grids

Abstract

We present three results on the multiset dimension of graphs, resolving one conjecture and two open questions from the literature. First, we disprove the conjecture of Simanjuntak, Siagian and Vetr\'ik (2017) that every graph $G$ of order $n(G)$ with finite multiset dimension satisfies $\dim_m(G) \le n(G)-1$: an exhaustive computation over all 1,018,690,328 connected graphs of orders 2 through 11 shows that exactly eight graphs attain $\dim_m(G)=n(G)$, all of order 11, so 11 is the smallest order at which the trivial upper bound is attained. This also answers a question from the recent survey of Farhan, Klav\v{z}ar, Kuziak and Yero. Second, we prove that $\dim_m(P_n \boxtimes P_n)=4$ for every $n \ge 5$, answering a question of Hakanen and Yero: after a $45^\circ$ change of coordinates the Chebyshev metric of the king grid becomes half the Manhattan metric on a parity sublattice, and four boundary inequalities reduce every potentially resolving three-landmark set to two geometric cases, in each of which we exhibit an explicit collision. Third, on king strips the parameter grows linearly: $\dim_m(P_3 \boxtimes P_n)=n$ for $n \ge 6$ (with the small cases determined exactly), where the lower bound rests on three local separation conditions and a finite min-plus transfer certificate whose equality case yields a finite automaton with a 19-state recurrent core, and the upper bound is an explicit landmark pattern of period three that works for every height. Combined with a blindness lower bound, $\dim_m(P_h \boxtimes P_n) = \Theta(n)$ for every fixed $h \ge 3$, so the constant answer on square king grids requires both dimensions to grow.