Gaps Below n in Multiset Resolving Spectra

Abstract

A set S of vertices of a connected graph is multiset resolving if every vertex has a distinct multiset of distances to S. We study graphs whose identification spectrum (the set of sizes of multiset resolving sets) contains the order n but skips the sizes just below it, and define the top gap g(G) as n minus the largest size of a proper multiset resolving set. This relates to Problems 2 and 6 of the 2026 survey by Farhan, Klavžar, Kuziak and Yero (arXiv:2607.10311). Main results:- Exactly 17 connected graphs on 10 vertices have top gap 3, and no graph on fewer vertices does; the smallest order with top gap 4 is 11.- Graphs with top gap 3 exist at every order from 10 to 48.- DDI graphs with top gap exactly 5 exist (orders 49 and 51–55), and graphs of order 52 with top gap exactly k for every k from 6 to 10.- The gap-10 graph was verified by three independently written programs, including a clean-room C++ checker that tested all 4,588,649,793 deletion sets of sizes 1 to 9.- Collision, Switch, Blocking, Persistence and Flow Lemmas explain the mechanism; a counting barrier limits switch-based designs.- As by-products, the conjecture dim_m(G) ≤ n − 1 holds for all connected graphs on at most 10 vertices, and dim_m(T) ≤ n − d + 1 holds for all trees on at most 15 vertices. We conjecture that the top gap is unbounded. The supplementary ZIP contains every graph in graph6 format, a plain Python verifier, the C enumeration program with logs, the independent clean-room verifier and its outputs, scripts for all sampling experiments with fixed random seeds, and SHA-256 checksums. Computations and drafting were assisted by the AI systems ChatGPT (OpenAI), Claude (Anthropic) and Grok (xAI), as described in the paper's acknowledgment.