Graphs with the edge metric dimension smaller than the metric dimension

Martin Knor, Snježana Majstorović, Aoden Teo Masa Toshi, Riste Škrekovski and Ismael G. Yero

Applied Mathematics and Computation, 2021, vol. 401, issue C

Abstract: Given a connected graph G, the metric (resp. edge metric) dimension of G is the cardinality of the smallest ordered set of vertices that uniquely identifies every pair of distinct vertices (resp. edges) of G by means of distance vectors to such a set. In this work, we settle three open problems on (edge) metric dimension of graphs. Specifically, we show that for every r,t≥2 with r≠t, there is n0, such that for every n≥n0 there exists a graph G of order n with metric dimension r and edge metric dimension t, which among other consequences, shows the existence of infinitely many graph whose edge metric dimension is strictly smaller than its metric dimension. In addition, we also prove that it is not possible to bound the edge metric dimension of a graph G by some constant factor of the metric dimension of G.

Keywords: Edge metric dimension; Metric dimension; Unicyclic graphs (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300321001247
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:401:y:2021:i:c:s0096300321001247

DOI: 10.1016/j.amc.2021.126076

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().