{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T10:03:11Z","timestamp":1771063391820,"version":"3.50.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T00:00:00Z","timestamp":1586304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Let $(X,d)$ be a metric space. A set $S\\subseteq X$ is said to be a $k$-metric generator for $X$ if and only if for any pair of different points $u,v\\in X$, there exist at least $k$ points $w_1,w_2, \\ldots w_k\\in S$ such that $d(u,w_i)\\ne d(v,w_i),\\; \\textrm{for all}\\; i\\in \\{1, \\ldots k\\}.$ Let $\\mathcal{R}_k(X)$ be the set of metric generators for $X$. The $k$-metric dimension $\\dim _k(X)$ of $(X,d)$ is defined as $$\\begin{equation*}\\dim_k(X)=\\inf\\{|S|:\\, S\\in \\mathcal{R}_k(X)\\}.\\end{equation*}$$Here, we discuss the $k$-metric dimension of $(V,d_t)$, where $V$ is the set of vertices of a simple graph $G$ and the metric $d_t:V\\times V\\rightarrow \\mathbb{N}\\cup \\{0\\}$ is defined by $d_t(x,y)=\\min \\{d(x,y),t\\}$ from the geodesic distance $d$ in $G$ and a positive integer $t$. The case $t\\ge D(G)$, where $D(G)$ denotes the diameter of $G$, corresponds to the original theory of $k$-metric dimension, and the case $t=2$ corresponds to the theory of $k$-adjacency dimension. Furthermore, this approach allows us to extend the theory of $k$-metric dimension to the general case of non-necessarily connected graphs. Finally, we analyse the computational complexity of determining the $k$-metric dimension of $(V,d_t)$ for the metric $d_t$.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa009","type":"journal-article","created":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T20:09:04Z","timestamp":1579291744000},"page":"707-720","source":"Crossref","is-referenced-by-count":15,"title":["On The (<i>k,t<\/i>)-Metric Dimension Of Graphs"],"prefix":"10.1093","volume":"64","author":[{"given":"A","family":"Estrada-Moreno","sequence":"first","affiliation":[{"name":"Departament d\u2019Enginyeria Inform\u00e0tica i Matem\u00e0tiques, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I G","family":"Yero","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Escuela Polit\u00e9cnica Superior de Algeciras Universidad de C\u00e1diz, Av. Ram\u00f3n Puyol s\/n, 11202 Algeciras, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J A","family":"Rodr\u00edguez-Vel\u00e1zquez","sequence":"additional","affiliation":[{"name":"Departament d\u2019Enginyeria Inform\u00e0tica i Matem\u00e0tiques, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,4,8]]},"reference":[{"key":"2021052810194652700_ref1","article-title":"An algorithm for the weighted metric dimension of two-dimensional grids","author":"Adar","year":"2016"},{"key":"2021052810194652700_ref2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10878-016-0073-1","article-title":"The $k$-metric dimension","volume":"34","author":"Adar","year":"2017","journal-title":"J. Comb. Optim."},{"key":"2021052810194652700_ref3","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.disopt.2015.06.001","article-title":"The weighted 2-metric dimension of trees in the non-landmarks model","volume":"17","author":"Adar","year":"2015","journal-title":"Discrete Optim."},{"key":"2021052810194652700_ref4","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s40315-013-0024-0","article-title":"The metric dimension of metric spaces","volume":"13","author":"Bau","year":"2013","journal-title":"Comput. Methods Funct. Theory"},{"key":"2021052810194652700_ref5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.26493\/1855-3974.1281.c7f","article-title":"On the $k$-metric dimension of metric spaces","volume":"16","author":"Beardon","year":"2019","journal-title":"Ars Math. Contemp."},{"key":"2021052810194652700_ref6","volume-title":"Theory and Applications of Distance Geometry","author":"Blumenthal","year":"1953"},{"key":"2021052810194652700_ref7","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.tcs.2018.09.022","article-title":"On the $k$-partition dimension of graphs","volume":"806","author":"Estrada-Moreno","journal-title":"Theoret. Comput. Sci."},{"key":"2021052810194652700_ref8","doi-asserted-by":"crossref","first-page":"102","DOI":"10.2298\/AADM151109022E","article-title":"On the adjacency dimension of graphs","volume":"10","author":"Estrada-Moreno","year":"2016","journal-title":"Appl. Anal. Discrete Math."},{"key":"2021052810194652700_ref9","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.endm.2014.08.017","article-title":"$k$-metric resolvability in graphs","volume":"46","author":"Estrada-Moreno","year":"2014","journal-title":"Electron. Notes Discrete Math."},{"key":"2021052810194652700_ref10","first-page":"2829","article-title":"The $k$-metric dimension of a graph","volume":"9","author":"Estrada-Moreno","year":"2015","journal-title":"Appl. Math. Inf. Sci."},{"key":"2021052810194652700_ref11","doi-asserted-by":"crossref","first-page":"1924","DOI":"10.1016\/j.disc.2015.12.024","article-title":"The $k$-metric dimension of the lexicographic product of graphs","volume":"339","author":"Estrada-Moreno","year":"2016","journal-title":"Discrete Math."},{"key":"2021052810194652700_ref12","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s40840-015-0282-2","article-title":"The $k$-metric dimension of corona product graphs","volume":"39","author":"Estrada-Moreno","year":"2016","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"2021052810194652700_ref13","article-title":"On the fractional metric dimension of corona product graphs and lexicographic product graphs","author":"Feng"},{"key":"2021052810194652700_ref14","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.dam.2017.11.019","article-title":"On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results","volume":"236","author":"Fernau","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"2021052810194652700_ref15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-06686-8_12","article-title":"Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results","volume-title":"Computer Science\u2014Theory and Applications","author":"Fernau","year":"2014"},{"key":"2021052810194652700_ref16","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/BF01844162","article-title":"On the corona of two graphs","volume":"4","author":"Frucht","year":"1970","journal-title":"Aequationes Math."},{"key":"2021052810194652700_ref17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00010-013-0207-9","article-title":"Coloring, location and domination of corona graphs","volume":"86","author":"Gonz\u00e1lez Yero","year":"2013","journal-title":"Aequationes Math."},{"key":"2021052810194652700_ref18","article-title":"Discrete Mathematics and its Applications","volume-title":"Handbook of Product Graphs","author":"Hammack","year":"2011"},{"key":"2021052810194652700_ref19","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"Harary","year":"1969"},{"key":"2021052810194652700_ref20","first-page":"191","article-title":"On the metric dimension of a graph","volume":"2","author":"Harary","year":"1976","journal-title":"Ars Combin."},{"key":"2021052810194652700_ref21","article-title":"Product Graphs, Structure and Recognition","volume-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization, New Jersey","author":"Imrich","year":"2000"},{"key":"2021052810194652700_ref22","first-page":"155","article-title":"On the metric dimension of corona product of graphs","volume":"52","author":"Iswadi","year":"2011","journal-title":"Far East J. Math. Sci."},{"key":"2021052810194652700_ref23","doi-asserted-by":"crossref","first-page":"3349","DOI":"10.1016\/j.disc.2012.07.025","article-title":"The metric dimension of the lexicographic product of graphs","volume":"312","author":"Jannesari","year":"2012","journal-title":"Discrete Math."},{"key":"2021052810194652700_ref24","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/j.dam.2018.05.051","article-title":"The fractional strong metric dimension in three graph products","volume":"251","author":"Kang","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"2021052810194652700_ref25","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.dam.2012.10.009","article-title":"On the strong metric dimension of corona product graphs and join graphs","volume":"161","author":"Kuziak","year":"2013","journal-title":"Discrete Appl. Math."},{"key":"2021052810194652700_ref26","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.7151\/dmgt.1911","article-title":"Closed formulae for the strong metric dimension of lexicographic product graphs","volume":"36","author":"Kuziak","year":"2016","journal-title":"Discuss. Math. Graph Theory"},{"key":"2021052810194652700_ref27","doi-asserted-by":"crossref","first-page":"2093","DOI":"10.1007\/s00373-016-1675-1","article-title":"The simultaneous metric dimension of families composed by lexicographic product graphs","volume":"32","author":"Ram\u00edrez-Cruz","year":"2016","journal-title":"Graphs Combin."},{"key":"2021052810194652700_ref28","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.dam.2015.06.012","article-title":"The simultaneous metric dimension of graph families","volume":"198","author":"Ram\u00edrez-Cruz","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"2021052810194652700_ref29","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/s40840-015-0283-1","article-title":"On the local metric dimension of corona product graphs","volume":"39","author":"Rodr\u00edguez-Vel\u00e1zquez","year":"2015","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"2021052810194652700_ref30","first-page":"387","article-title":"The partition dimension of corona product graphs","volume":"127","author":"Rodr\u00edguez-Vel\u00e1zquez","year":"2016","journal-title":"Ars Combin."},{"key":"2021052810194652700_ref31","first-page":"216","article-title":"Transitivit\u00e9 et connexit\u00e9","volume":"249","author":"Roy","year":"1959","journal-title":"C. R. Acad. Sci. Paris"},{"key":"2021052810194652700_ref32","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1016\/j.disc.2013.01.021","article-title":"The metric dimension of the lexicographic product of graphs","volume":"313","author":"Saputro","year":"2013","journal-title":"Discrete Math."},{"key":"2021052810194652700_ref33","first-page":"549","article-title":"Leaves of trees","volume":"14","author":"Slater","year":"1975","journal-title":"Congr. Numer."},{"key":"2021052810194652700_ref34","first-page":"445","article-title":"Dominating and reference sets in a graph","volume":"22","author":"Slater","year":"1988","journal-title":"J. Math. Phys. Sci."},{"key":"2021052810194652700_ref35","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A theorem on boolean matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"J. ACM"},{"key":"2021052810194652700_ref36","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.amc.2016.12.005","article-title":"Computing the $k$-metric dimension of graphs","volume":"300","author":"Yero","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"2021052810194652700_ref37","doi-asserted-by":"crossref","first-page":"2793","DOI":"10.1016\/j.camwa.2011.03.046","article-title":"On the metric dimension of corona product graphs","volume":"61","author":"Yero","year":"2011","journal-title":"Comput. Math. Appl."},{"key":"2021052810194652700_ref38","first-page":"163","article-title":"On some properties of linear complexes","volume":"24","author":"Zykov","year":"1949","journal-title":"Mat. Sb."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/707\/38334923\/bxaa009.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/707\/38334923\/bxaa009.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T11:54:53Z","timestamp":1622202893000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/5\/707\/5808798"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,8]]},"references-count":38,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,4,8]]},"published-print":{"date-parts":[[2021,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa009","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5]]},"published":{"date-parts":[[2020,4,8]]}}}