On the Cover Time of Random Geometric Graphs

The cover time of graphs has much relevance to algorithmic applications and has been extensively investigated. Recently, with the advent of ad-hoc and sensor networks, an interesting class of random graphs, namely

random geometric graphs

, has gained new relevance and its properties have been the subject of much study. A random geometric graph

${\mathcal G}(n,r)$

is obtained by placing

n

points uniformly at random on the unit square and connecting two points iff their Euclidean distance is at most

r

. The phase transition behavior with respect to the radius

r

of such graphs has been of special interest. We show that there exists a critical radius

r

opt

such that for any

$r \geq r_{\rm opt} {\mathcal G}(n,r)$

has optimal cover time of Θ(

n

log

n

) with high probability, and, importantly,

r

opt

 = Θ(

r

con

) where

r

con

denotes the critical radius guaranteeing asymptotic connectivity. Moreover, since a disconnected graph has infinite cover time, there is a phase transition and the corresponding threshold width is

O

(

r

con

). We are able to draw our results by giving a tight bound on the electrical resistance of

${\mathcal G}(n,r)$

via the power of certain constructed flows.