[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the cover time of random walks on graphs

  • Published:
Journal of Theoretical Probability Aims and scope Submit manuscript

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 ofO(n 2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., and Rackoff, C. (1979). Random walks, universal traversal sequences, and the complexity of maze problems, 20'th FOCS.

  2. Welsh, D. J. A. (1976).Matroid Theory. Academic Press, London.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Rutgers University, New Brunswick, New Jersey

    Jeff D. Kahn & Michael E. Saks

  2. IBM Almaden, 650 Harry Road, 95120, San Jose, California

    Nathan Linial

  3. Computer Science Department, Hebrew University, Jerusalem, Israel

    Nathan Linial

  4. Computer Science Division, University of California, Berkeley, California

    Noam Nisan

  5. Bell Communications Research, Morristown, New Jersey

    Michael E. Saks

Authors
  1. Jeff D. Kahn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nathan Linial
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Noam Nisan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael E. Saks
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kahn, J.D., Linial, N., Nisan, N. et al. On the cover time of random walks on graphs. J Theor Probab 2, 121–128 (1989). https://doi.org/10.1007/BF01048274

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01048274

Key Words

Search

Navigation