Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and vc dimension^∗

The metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to upper-bound the order n of a graph in terms of its diameter d and metric dimension k. In general, the bound n ≤ d^k + k is known to hold. We prove a bound of the form n = O(kd²) for trees and outerplanar graphs (for trees we determine the best possible bound and the corresponding extremal examples). More generally, for graphs having a tree decomposition of width w and length , we obtain a bound of the form n = O(kd²(2 + 1)³w⁺¹). This implies in particular that n = O(kd^{O (1)}) for graphs of constant treewidth and n = O(f(k)d²) for chordal graphs, where f is a doubly exponential function. Using the notion of distance-VC dimension (introduced in 2014 by Bousquet and Thomassé) as a tool, we prove the bounds n ≤ (dk+1)^t−¹ +1 for Kt-minor-free graphs and n ≤ (dk+1)^d(3·^2r+2) +1 for graphs of rankwidth at most r.