Published October 14, 2013
| Version v1
Journal article
Metric dimension for random graphs
- Creators
- Bollobas, Bela
- Mitsche, Dieter
- Pralat, Pawel
- Others:
- Department of Applied Mathematics and Theoretical Physics (DAMTP) ; University of Cambridge [UK] (CAM)
- Laboratoire Jean Alexandre Dieudonné (JAD) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Department of Mathematics ; Ryerson University [Toronto]
Description
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)$.
Abstract
International audience
Additional details
- URL
- https://hal.archives-ouvertes.fr/hal-00914127
- URN
- urn:oai:HAL:hal-00914127v1
- Origin repository
- UNICA