2016/10/31 by Laurent Beaudou, Peter Dankelmann, Florent Foucaud +3 · 12 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Dimension (graph theory) #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Line graph #Mathematical analysis #Mathematics #Metric dimension #Order (exchange) #Pathwidth #Treewidth #Upper and lower bounds #Vertex (graph theory) #math.CO
paper · pdf · doi:10.1137/16m1097833
published in SIAM Journal on Discrete Mathematics 32(2), 902-918 (Society for Industrial and Applied Mathematics) · 15 pages, 2 figures
openalex publication_date 2018/01/01 · arxiv created 2018/07/20 · arxiv updated 2018/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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≤ dk+k is known to hold. We prove a bound of the form n=O(kd2) 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(kd2(2ℓ+1)3w+1). This implies in particular that n=O(kdO(1)) for graphs of constant treewidth and n=O(f(k)d2) 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.