Asymptotic behavior of the edge metric dimension of the random graph

DOI10.7151/DMGT.2210MaRDI QIDQ2227114zbMATH OpenOpenAlexWikidataFDO

Authors Nina Zubrilina

Publication date 10 February 2021

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://doi.org/10.7151/dmgt.2210

zbMATH Keywords

edge dimensionrandom graphSuen inequality

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Review text

A set \(S\subseteq V(G)\) is an edge metric generator for a graph \(G\) if for any two edges \(e\) and \(f\) of \(G\) there is a vertex \(x\in S\) such that \(d(x, e) \ne d(x, f)\). The minimum cardinality of an edge metric generator for \(G\) is the edge metric dimension \(\mathrm{edim}(G)\) of \(G\). It is proved that if \(G(n,p)\) is the Erdős-Rényi random graph with constant \(p\), then \(\mathrm{edim}(G(n,p)) = (1+o(1))\frac{4\log n}{\log (1/q)}\), where \(q=1-2p(1-p)^2(2-p)\).

Recommendations

• Metric dimension for random graphs
• On the edge dimension of a graph
• Graphs with the edge metric dimension smaller than the metric dimension
• On the edge metric dimension of graphs
• Uniquely identifying the edges of a graph: the edge metric dimension

Cites work

• A Matrix Reduction Problem
• Edge metric dimension of some generalized Petersen graphs
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Landmarks in graphs
• Metric bases in digital geometry
• Metric dimension for random graphs
• New versions of Suen's correlation inequality
• On the edge dimension of a graph
• Resolvability and the upper dimension of graphs
• Resolvability in graphs and the metric dimension of a graph
• Structure-activity maps for visualizing the graph variables arising in drug design
• Uniquely identifying the edges of a graph: the edge metric dimension

Cited in

(11)

• Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
• On the edge metric dimension of graphs
• Metric dimension for random graphs
• Sequential metric dimension for random graphs
• scientific article; zbMATH DE number 7560302 (Why is no real title available?)
• On approximation algorithm for the edge metric dimension problem
• Edge metric dimension of silicate networks
• Metric dimensions of generalized Sierpiński graphs over squares
• On some families of path-related graphs with their edge metric dimension
• Throttling for metric dimension and its variants
• Metric and edge metric dimensions of generalized Andrásfai graphs

This page was built for publication: Asymptotic behavior of the edge metric dimension of the random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227114)