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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
You do it in two steps:
First you think of a graph which you can expect to be difficult.
Then you prove your suspicion.
Let's start with the first step - do you have any graph in mind?