On the cover time of random walks on graphs | Zendy

Jeff D. Kahn | Zendy; Nathan Linial | Zendy; Noam Nisan | Zendy; Michael Saks | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the cover time of random walks on graphs

Author(s) -

Jeff D. Kahn,

Nathan Linial,

Noam Nisan,

Michael Saks

Publication year - 1989

Publication title -

journal of theoretical probability

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.671

H-Index - 42

eISSN - 1572-9230

pISSN - 0894-9840

DOI - 10.1007/bf01048274

Subject(s) - mathematics , combinatorics , cover (algebra) , random regular graph , upper and lower bounds , random walk , random graph , discrete mathematics , indifference graph , chordal graph , graph , 1 planar graph , statistics , mechanical engineering , mathematical analysis , engineering

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of O(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research