The cover time of two classes of random graphs
Colin Cooper, ALAN M. FRIEZE · Research Portal (King's College London) · 2005
Let G = (V,E) be a connected graph, let |V| = n, and |E| = m.A random walk Wu, u ∈ V on the undirected graph G = (V, E) is a Markov chain X0 = u, X1,...Xt,... ∈ V associated to a particle that moves from vertex to vertex according to the following rule: the probability of a transition from vertex i, of degree di, to vertex j is 1/di if {i,j} ∈ E, and 0 otherwise. For u ∈ V let Cu be the expected time taken for Wu to visit every vertex of G. The cover time CG of G is defined as CG = maxu∈V Cu. The cover time of connected graphs has been extensively studied. It is a classic result of Aleliunas, Karp, Lipton, Lovasz and Rackoff [2] that CG ≤ 2m(n - 1). It was shown by Feige [11], [12], that for any connected graph G[EQUATION]The lower bound is achieved by (for example) the complete graph Kn, whose cover time is determined by the Coupon Collector problem.