Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

ON THE RELATION BETWEEN GRAPH DISTANCE AND EUCLIDEAN DISTANCE IN RANDOM GEOMETRIC GRAPHS

Abstract : Given any two vertices u, v of a random geometric graph G(n, r), denote by d_E(u, v) their Euclidean distance and by d_G(u, v) their graph distance. The problem of finding upper bounds on d_G(u, v) conditional on d_E(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper, we improve the known upper bounds for values of r = \omega\sqrt(log n)) (i.e. for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on d_G(u, v) conditional on d_E(u, v).
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01291932
Contributor : Dieter Mitsche Connect in order to contact the contributor
Submitted on : Tuesday, March 22, 2016 - 12:23:03 PM
Last modification on : Saturday, June 25, 2022 - 11:18:57 PM
Long-term archiving on: : Sunday, November 13, 2016 - 10:44:41 PM

File

distancies-final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01291932, version 1

Collections

Citation

Josep Diaz, Dieter Mitsche, Guillem Perarnau, Xavier Pérez-Giménez. ON THE RELATION BETWEEN GRAPH DISTANCE AND EUCLIDEAN DISTANCE IN RANDOM GEOMETRIC GRAPHS. Advances in Applied Probability, Applied Probability Trust, 2016. ⟨hal-01291932⟩

Share

Metrics

Record views

52

Files downloads

74