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
amir.yehudayoff@gmail.com


July 28, 2012

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.

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]