Metric dimension for random graphs

zbMATH Open1295.05095MaRDI QIDQ396907FDOQ396907

Authors Béla Bollobás, D. Mitsche, Paweł Prałat

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.3801

zbMATH Keywords

diametermetric dimensionrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Abstract: The metric dimension of a graph $G$ is the minimum number of vertices in a subset $S$ of the vertex set of $G$ such that all other vertices are uniquely determined by their distances to the vertices in $S$. In this paper we investigate the metric dimension of the random graph $G(n,p)$ for a wide range of probabilities $p=p(n)$.

Recommendations

• Metric models for random graphs
• Sequential metric dimension for random graphs
• Asymptotic behavior of the edge metric dimension of the random graph
• Infinite random graphs and properties of metrics
• Measures on the Random Graph
• Metric structure of random networks
• Diameters of random distance graphs
• The Vapnik-Chervonenkis dimension of a random graph
• Mixed metric dimension of graphs
• Large random graphs in pseudo-metric spaces

Cited in

(16)

• The localization game on oriented graphs
• Asymptotic behavior of the edge metric dimension of the random graph
• Edge and pair queries-random graphs and complexity
• On the robustness of the metric dimension of grid graphs to adding a single edge
• Metric dimension for amalgamations of graphs
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Extending the metric dimension to graphs with missing edges
• A note on the localization number of random graphs: diameter two case
• Localization game for random graphs
• A metric graph for which the number of possible end positions of a random walk grows minimally
• scientific article; zbMATH DE number 7589564 (Why is no real title available?)
• Localization game for random geometric graphs
• Metric dimension of Andrásfai graphs
• Sequential metric dimension for random graphs
• On the limiting distribution of the metric dimension for random forests
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications

This page was built for publication: Metric dimension for random graphs

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