Asymptotic Behavior of the Edge Metric Dimension of the Random Graph

Abstract

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

Keywords

• random graph
• edge dimension
• suen’s inequality
• 05c12
• 05c80