Metric Dimension for Random Graphs

  • Béla Bollobás
  • Dieter Mitsche
  • Paweł Prałat
DOI: https://doi.org/10.37236/2639
Keywords: random graphs, metric dimension, diameter

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

Published
2013-10-14
How to Cite
Bollobás, B., Mitsche, D., & Prałat, P. (2013). Metric Dimension for Random Graphs. The Electronic Journal of Combinatorics, 20(4), P1. https://doi.org/10.37236/2639
Issue
Volume 20, Issue 4 (2013)
Article Number
P1