Chicago Journal of Theoretical Computer Science

Volume 2012

Article 3

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

Linear cover time for trees is exponentially unlikely

Amir Yehudayoff
Department of Mathematics
Technion, IIT
Haifa, Israel

July 28, 2012


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.

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

DOI: 10.4086/cjtcs.2012.003

[] Volume 2012, Article 2 [] Volume 2012, Article 4
[back] Volume 2012 [back] Published articles
[CJCTS home]