On the relation between graph distance and Euclidean distance in random geometric graphs
On the relation between graph distance and Euclidean distance in random geometric graphs
复制标题
论随机几何图中图距离与欧氏距离的关系
DOI：
--
复制
发表时间：
2014
影响因子：
1.2
通讯作者：
X. Pérez
中科院分区：
文献类型：
--
作者：
J. Díaz;D. Mitsche;G. Perarnau;X. Pérez
给定随机几何图G（n，r）的任意两个顶点u，v，用dE（u，v）表示它们的欧氏距离，用dE（u，v）表示它们的图距离。在dE（u，v）的条件下求dG（u，v）的渐近几乎必然成立的上界问题在文献中得到了相当多的关注。在本文中，我们改进了已知的上界r=ω（logn）的值（也就是说，对于r以上的连通性阈值）。我们的结果也改进了随机几何图直径的最佳已知估计。我们还提供了dE（u，v）的一个下界，条件是dE（u，v）.
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 E (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=ω(√logn) (that is, 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 E (u, v) conditional on d E (u, v).