About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
On the cover time of random walks on graphs
Abstract
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 of O(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n log n) for the expected cover time for trees. We present examples showing all our bounds to be tight. © 1989 Plenum Publishing Corporation.