Metric dimension for random graphs

zbMATH Open1295.05095arXiv1208.3801MaRDI 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)

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)$.

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

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

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)

Cited In (17)

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

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)