Geodesic
Asymptotic Behavior of the Edge Metric Dimension of the Random Graph
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 589-599

Voir la notice de l'article provenant de la source Library of Science

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))4 log n/log(1/q), where q = 1 − 2p(1 − p)^2(2 − p).
Keywords: random graph, edge dimension, Suen’s inequality 
Zubrilina, Nina. Asymptotic Behavior of the Edge Metric Dimension of the Random Graph. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 589-599. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a14/
@article{DMGT_2021_41_2_a14,
     author = {Zubrilina, Nina},
     title = {Asymptotic {Behavior} of the {Edge} {Metric} {Dimension} of the {Random} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {589--599},
     year = {2021},
     volume = {41},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a14/}
}
TY  - JOUR
AU  - Zubrilina, Nina
TI  - Asymptotic Behavior of the Edge Metric Dimension of the Random Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 589
EP  - 599
VL  - 41
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a14/
LA  - en
ID  - DMGT_2021_41_2_a14
ER  - 
%0 Journal Article
%A Zubrilina, Nina
%T Asymptotic Behavior of the Edge Metric Dimension of the Random Graph
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 589-599
%V 41
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a14/
%G en
%F DMGT_2021_41_2_a14

[1] B. Bollobás, D. Mitsche and P. Pralat, Metric dimension for random graphs, (2012). arXiv:1208.3801

[2] G. Chartrand, C. Poisson and P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl. 39 (2000) 19–28. doi:10.1016/S0898-1221(00)00126-7

[3] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113. doi:10.1016/S0166-218X(00)00198-0

[4] V. Filipović, A. Kartelj and J. Kratica, Edge metric dimension of some generalized Petersen graphs, Results Math. 74 (2019) Article 182.

[5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.

[6] S. Janson, New versions of Suen’s correlation inequality, Random Structures Algorithms 13 (1998) 467–483. doi:10.1002/(SICI)1098-2418(199810/12)13:3/4〈467::AID-RSA15〉3.0.CO;2-w

[7] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist. 3 (1993) 203–236. doi:10.1080/10543409308835060

[8] A. Kelenc, N. Tratnik and I.G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Appl. Math. 251 (2018) 204–220. doi:10.1016/j.dam.2018.05.052

[9] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. doi:10.1016/0166-218X(95)00106-2

[10] R.A. Melter and I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing 25 (1984) 113–121. doi:10.1016/0734-189X(84)90051-3

[11] J.W. Moon and L. Moser, A matrix reduction problem, Math. Comp. 20 (1966) 328–330. doi:10.1090/S0025-5718-66-99935-2

[12] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.

[13] N. Zubrilina, On the edge dimension of a graph, Discrete Math. 341 (2018) 2083–2088. doi:10.1016/j.disc.2018.04.010