Graphs attaining dimₘ(G)=n(G) at orders 12 and 13, with certified multiset dimensions of king grids

Abstract

The multiset dimension dimₘ(G) of a graph G is the least size of a landmark set S ⊆ V(G) for which the multiset of distances from a vertex to S — the landmark labels forgotten — determines the vertex, and ∞ when no landmark set does. Simanjuntak, Siagian and Vetrík conjectured that the trivial bound dimₘ(G) ≤ n(G) is never attained. Allikvere refuted the conjecture by an exhaustive scan through order 11, which produced exactly eight extremal graphs, all of order 11; he then asked whether an extremal graph exists for every n ≥ 11, reporting that his own one-vertex extension search at order 12 found none. We answer that question affirmatively at n=12 and at n=13, by two explicit graphs of 30 and 35 edges and diameter 3 in which the full vertex set is the only multiset resolving set. They were found by extending seeds that the earlier search discarded: the order-12 witness descends from an order-11 graph whose own full vertex set does not resolve. Alongside, we certify individual cells of Allikvere's king-grid theorems and the non-monotonicity of the height-four row dimₘ(P₄boxtimes Pₙ), and we bound by 7 four cells that his table leaves as >6 and that an exhaustive search outside the verified development puts at exactly 7. Every value we certify is a witness together with an exhaustion of all smaller landmark sets, and every statement of the paper is formally verified in Lean 4; the few numbers that come from the unverified search are marked as such where they appear.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   a7cb16212790f015432911026db57f3d80b652898328c3467f51c54ea5f305b6