Premium
The cover time of random geometric graphs
Author(s) -
Cooper Colin,
Frieze Alan
Publication year - 2011
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
ISBN - 978-0-89871-698-6
DOI - 10.1002/rsa.20320
Subject(s) - combinatorics , mathematics , torus , random walk , ball (mathematics) , vertex (graph theory) , random geometric graph , geometry , unit sphere , graph , random graph , cover (algebra) , discrete mathematics , statistics , mechanical engineering , voltage graph , line graph , engineering
We study the cover time of random geometric graphs. Let $I(d)=[0,1]^{d}$ denote the unit torus in d dimensions. Let $D(x,r)$ denote the ball (disc) of radius r . Let $\Upsilon_d$ be the volume of the unit ball $D(0,1)$ in d dimensions. A random geometric graph $G=G(d,r,n)$ in d dimensions is defined as follows: Sample n points V independently and uniformly at random from $I(d)$ . For each point x draw a ball $D(x,r)$ of radius r about x . The vertex set $V(G)=V$ and the edge set $E(G)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G . Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies$$C_G\sim c\log \left({{c}\over{c-1}}\right)n\log n.$$ © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011