DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

N. Zubrilina

Title:

Asymptotic behavior of the edge metric dimension of the random graph

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-10-10, Revised: 2019-02-09, Accepted: 2019-02-09, https://doi.org/10.7151/dmgt.2210

Abstract:

Given a simple connected graph $G(V, E)$, the edge metric dimension, denoted 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 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<br> edim$(G(n, p)) = (1 + o(1))\frac{4\log n}{\log(1/q)}, $ where $q = 1 - 2p(1-p)^2(2-p)$.

Keywords:

random graph, edge dimension, Suen’s inequality

PDF
Close