Graphs with the edge metric dimension smaller than the metric dimension

DOI10.1016/J.AMC.2021.126076arXiv2006.11772MaRDI QIDQ6343374

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

Publication date: 21 June 2020

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,tge2$ with $ret$, there is $n_0$, such that for every $nge{n}_0$ 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$.

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: Graphs with the edge metric dimension smaller than the metric dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343374)