Cover time
In mathematics, the cover time of a finite Markov chain is the number of steps taken by the chain, from a given starting state, until the first step at which all states have been reached. It is a random variable that depends on the Markov chain and the choice of the starting state. The cover time of a connected undirected graph is the cover time of the Markov chain that takes a random walk on the graph, at each step moving from one vertex to a uniformly-random neighbor of that vertex.
Applications
Cover times of graphs have been extensively studied in theoretical computer science for applications involving the complexity of st-connectivity, algebraic [graph theory] and the study of expander graphs, and modeling token ring computer networking technology.
In different classes of graphs
A classical problem in probability theory, the coupon collector's problem, can be interpreted as the result that the expected cover time of a complete graph is. For every other -vertex graph, the expected cover time is at least as large as this formula. Any -vertex regular expander graph also has expected cover time from any starting vertex, and more generally the cover time of any regular graph is where is the second-largest eigenvalue of the graph, normalized so that the largest eigenvalue is one. For arbitrary -vertex graphs, from any starting vertex, the cover time is at most and there exist graphs whose expected cover time is this large. In planar graphs, the expected cover time is and.