## Random Geometric Graph Diameter in the Unit Disk with ℓp Metric (Extended Abstract)
Ellis, Robert and Martin, Jeremy and Yan, Catherine
(2004)
Full text not available from this repository. ## AbstractLet n be a positive integer, λ> 0 a real number, and 1≤ p≤ ∞. We study the unit disk random geometric graphG p (λ,n), defined to be the random graph on n vertices, independently distributed uniformly in the standard unit disk in R2, with two vertices adjacent if and only if their ℓ p -distance is at most λ. Let λ = c ln n/n, and let ap be the ratio of the (Lebesgue) areas of the ℓ p- and ℓ2-unit disks. Almost always, G p (λ,n) has no isolated vertices and is also connected if c>a p − − 1/2, and has n1−apc2(1+o(1)) isolated vertices if c<ap–1/2. Furthermore, we find upper bounds (involving λ but independent of p) for the diameter of G p (λ,n), building on a method originally due to M. Penrose.
Repository Staff Only: item control page References |