Asymptotic Behavior of the Edge Metric Dimension of the Random Graph

Given a simple connected graph $G(V,E)$, the edge metric dimension, denoted \(edim(G)\), is the least size of a set $S ⊆ V$ that distinguishes every pair of edges of $G$, in the sense that the edges have pairwise different tuples of distances to the vertices of $S$. In this paper we prove that the edge metric dimension of the Erdős-Rényi random graph $G(n, p)$ with constant $p$ is given by \[edim(G(n,p))=(1+o(1))\frac{4 \log n}{\log(1/q)},\] where $q = 1 − 2p(1 − p)^2(2 − p)$.