Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?

The cover time is the expected length of a random walk that visits all vertices.

share|cite|improve this question
What is the "cover time"? – Raphael Jun 22 '12 at 14:57
I think cover time means the expected number of steps taken by a random walk to visit every vertex. – Juho Jun 22 '12 at 21:19
You also have to assume that the graph is strongly connected. – Yuval Filmus Jan 27 '13 at 6:38

1 Answer 1

You do it in two steps:

  1. First you think of a graph which you can expect to be difficult.

  2. Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?

share|cite|improve this answer
To a novice, it might not be at all obvious that when you say “think of a graph”, you really mean “for all $n$ [or at least an infinite number of integers $n$], think of a graph of size $n$” and “prove your suspicion” involves computing the cover size in terms of $n$ and finding an expression that is exponential in $n$. A hint that isn't even didactic is really not useful. – Gilles Jan 14 at 19:13
@Gilles Why don't you add your own answer, then? – Yuval Filmus Jan 14 at 20:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.