Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension

Abstract

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\le d^k+k$ is known to hold. We prove a bound of the form $n=\mathcal{O}(k{d}^2)$ 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 $\ell$, we obtain a bound of the form $n=\mathcal{O}(k{d}^2(2\ell +1{)}^{3w+1})$. This implies in particular that $n=\mathcal{O}(k{d}^{\mathcal{O}(1)})$ for graphs of constant treewidth and $n=\mathcal{O}(f(k)d^2)$ 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\le (dk+1{)}^{t-1}+1$ for $K_t$-minor-free graphs, and $n\le (dk+1{)}^{d(3\cdot 2^r+2)}+1$ for graphs of rankwidth at most $r$.

15 pages, 2 figures

References in corpus (3)

• Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
• Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
• Identifying codes in hereditary classes of graphs and VC-dimension

Cited by in corpus (4)

• Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
• Sample compression schemes for balls in graphs
• Neighborhood complexity of planar graphs
• Metric dimension of maximal outerplanar graphs