{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T04:44:53Z","timestamp":1790743493428,"version":"4.1.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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\\leq d^k+k$ is known to hold. We prove a bound of the form $n=\\mathcal{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 $\\ell$, we obtain a bound of the form $n=\\mathcal{O}(kd^2(2\\ell+1)^{3w+1})$. This implies in particular that $n=\\mathcal{O}(kd^{\\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\u00e9) as a tool, we prove the bounds $n\\leq (dk+1)^{t-1}+1$ for $K_t$-minor-free graphs and $n\\leq (dk+1)^{d(3\\cdot 2^{r}+2)}+1$ for graphs of rankwidth at most $r$.<\/jats:p>","DOI":"10.1137\/16m1097833","type":"journal-article","created":{"date-parts":[[2018,4,19]],"date-time":"2018-04-19T10:28:55Z","timestamp":1524133735000},"page":"902-918","source":"Crossref","is-referenced-by-count":11,"title":["Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension"],"prefix":"10.1137","volume":"32","author":[{"given":"Laurent","family":"Beaudou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Dankelmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael A.","family":"Henning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnaud","family":"Mary","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aline","family":"Parreau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.5802\/aif.938"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdq096"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22212-2_24"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.884015"},{"key":"atypb5","first-page":"9","author":"Behtoei A.","year":"2017","journal-title":"Discrete Math. Algorithms Appl."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_10"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.04.003"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. A. Bondy,\n                      Induced subsets\n                      , J. Combin. Theory Ser. B, 12 (1972), pp. 201-202.","DOI":"10.1016\/0095-8956(72)90025-1"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/14097879X"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.05.026"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2008.2.403"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00198-0"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"V. Chva\u0301tal,\n                      Mastermind\n                      , Combinatorica, (1983), pp. 325-329.","DOI":"10.1007\/BF02579188"},{"key":"atypb14","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/978-3-642-33090-2_37","volume":"7501","author":"Diaz J.","year":"2012","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.060"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9896-2"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.01.006"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0184-1"},{"key":"atypb19","first-page":"191","volume":"2","author":"Harary F.","year":"1976","journal-title":"Ars Combin."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.37236\/302"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00106-2"},{"key":"atypb22","first-page":"75","volume":"22","author":"Re\u0301nyi A.","year":"1961","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0070"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48518-X_4"},{"key":"atypb29","first-page":"549","volume":"14","author":"Slater P. J.","year":"1975","journal-title":"Congr. Numer."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1097833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:30Z","timestamp":1787317530000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1097833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1097833"],"URL":"https:\/\/doi.org\/10.1137\/16m1097833","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}