Metric Dimension for Random Graphs

Béla Bollobás, Dieter Mitsche, Paweł Prałat

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


Keywords


random graphs, metric dimension, diameter

Full Text: PDF