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

Original language | English |
---|---|

Pages (from-to) | 902-918 |

Number of pages | 17 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 32 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2018 |

## Keywords

- Graph theory
- Metric dimension
- VC dimension

## ASJC Scopus subject areas

- General Mathematics

## Fingerprint

Dive into the research topics of 'Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and vc dimension^{∗}'. Together they form a unique fingerprint.