Published by the Department of Computer Science, The University of Chicago.

Abstract

The cover time of a graph is the time it takes for a random walk on it to visit all vertices. This note shows that for any tree on n vertices, the probability that the cover time of the tree is linear in n is exponentially small in n. This is true for any starting vertex.

• The article: PDF (159 Kbytes)
• Source material: ZIP (72 Kbytes)
• BibTeX entry for this article (246 bytes)

Submitted November 26, 2010, revised June 20, 2012, 2, published July 1, 2012.

© 2012 Amir Yehudayoff
Licensed under a Creative Commons Attribution License

Volume 2012, Article 2

Volume 2012, Article 4

Volume 2012

Published articles