Carnegie Mellon University
Browse

The cover time of random geometric graphs

Download (264.12 kB)
journal contribution
posted on 2009-08-19, 00:00 authored by Colin Cooper, Alan FriezeAlan Frieze

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 Υ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 6= v, w ∈ D(v, r)}. Let G(d, r, n), d ≥ 3 be a random geometric graph. Let CG denote the cover time of a simple random walk on G. Let c > 1 be constant, and let r = (c log n/(Υdn))1/d. Then whp the cover time satisfies CG ∼ c log (c/c − 1)n log n

History

Publisher Statement

This is the accepted version of the article which has been published in final form at http://dx.doi.org/10.1002/rsa.20320

Date

2009-08-19

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC