Uniquely identifying the edges of a graph: the edge metric dimension

Aleksander Kelenc, Niko Tratnik, Ismael G. Yero

Published 2016-01-31Version 1

Let $G=(V,E)$ be a connected graph, let $v\in V$ be a vertex and let $e=uw\in E$ be an edge. The distance between the vertex $v$ and the edge $e$ is given by $d_G(e,v)=\min\{d_G(u,v),d_G(w,v)\}$. A vertex $w\in V$ distinguishes two edges $e_1,e_2\in E$ if $d_G(w,e_1)\ne d_G(w,e_2)$. A set $S$ of vertices in a connected graph $G$ is an edge metric generator for $G$ if every two edges of $G$ are distinguished by some vertex of $S$. The smallest cardinality of an edge metric generator for $G$ is called the edge metric dimension and is denoted by $edim(G)$. In this article we introduce the concept of edge metric dimension and initiate the study of its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the edge metric dimension and the standard metric dimension of graphs. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present some bounds and closed formulae for the edge metric dimension of several classes of graphs.