On Edge Dimension of a Graph

Abstract

Given a connected graph $G(V,E)$, the edge dimension, denoted $\mathrm{edim}(G)$, is the least size of a set $S\subseteq V$ that distinguishes every pair of edges of $G$, in the sense that the edges have pairwise distinct tuples of distances to the vertices of $S$. The notation was introduced by Kelenc, Tratnik, and Yero, and in their paper, they asked several questions about properties of $\mathrm{edim}$. In this article we answer two of these questions: we classify the graphs for which $\mathrm{edim}(G)=n-1$ and show that $\frac{\mathrm{edim}(G)}{\dim (G)}$ isn't bounded from above (here $\dim (G)$ is the standard metric dimension of $G$). We also compute $\mathrm{edim}(G\square P_m)$ and $\mathrm{edim}(G+K_1)$.