Ellis, Robert and Martin, Jeremy and Yan, Catherine (2004) Random Geometric Graph Diameter in the Unit Disk with \ellp Metric (Extended Abstract). [Conference Paper]
Full text not available from this repository.
Abstract
Let n be a positive integer, $\lambda>0$ a real number, and 1le ple infin. We study the unit disk random geometric graph Gp(lambda,n), defined to be the random graph on n vertices, independently distributed uniformly in the standard unit disk in ${\mathbb R}^2$, with two vertices adjacent if and only if their ellp-distance is at most lambda. Let $\lambda=c\sqrt{\ln n/n}$, and let ap be the ratio of the (Lebesgue) areas of the ellp- and ell2-unit disks. Almost always, Gp(lambda,n) has no isolated vertices and is also connected if c>ap–1/2, and has $n^{1-a_pc^2}(1+o(1))$ isolated vertices if c<ap–1/2. Furthermore, we find upper bounds (involving lambda but independent of p) for the diameter of Gp(lambda,n), building on a method originally due to M. Penrose.
| Item Type: | Conference Paper |
|---|---|
| Classifications: | A General Literature > A.001 Introductory and Survey |
| ID Code: | 583 |
| Deposited By: | Selbach, Anna |
| Deposited On: | 23 Aug 2005 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=167 |
Repository Staff Only: item control page
