Maximum number of vertices in every metric basis

The problem asks how many vertices can be forced to occur in every metric basis of a connected graph; it was posed by Bagheri and collaborators around 2016. The 2021 literature left sharpness of the main bound unresolved.

Known results

• Hakanen, Junnila, Laihonen et al., 2021: if $k>0$ vertices belong to every metric basis of a connected graph with $n$ vertices, then $k\le n-\dim(G)-1$.
• The same paper derives $k\le (n-1)/2$.
• It reports no construction attaining the latter bound, while examples attain $k=n-\dim(G)-2$ with $k=2$.
• For $n\ge 6$, the corresponding edge bound is $|E(G)|\le n(n-1)/2-4$; equality is characterized by $\overline{G}\simeq P_{5}\cup\overline{K}_{n-5}$.

August 25, 2026 claimed resolution

A new preprint, On the Maximum Number of Vertices that Belong to Every Metric Basis, claims a stronger metric-dimension bound, proves attainability, and derives the order-only answer to the Bagheri question. The claim is not independently verified in the retrieved material.

Current status (as of August 2026): The classical bounds are established, while the new sharper bound, its attainability, and the resulting order-only maximum are claimed by the August 2026 preprint but remain unverified.