| On the Cover Time of Planar Graphs (2000) | |||||||||||||||
Abstract | |||||||||||||||
| The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex, connected graph is at least \Gamma 1 + o(1) \Delta n log n and at most \Gamma 1 + o(1) \Delta 4 27 n 3 . This paper proves that for bounded-degree planar graphs the cover time is at least cn(log n) 2 , and at most 6n 2 , where c is a positive constant depending only on the maximal degree of the graph. 1 Introduction Let G = (V; E) be a finite, connected, n-vertex graph and let fX k g 1 k=0 be a simple random walk on G. For each v 2 V , set T v = minfk 2 N : X k = vg and set C = max v2V T v . The cover time is defined as E v C, where E v denotes expectation with respect to the probability measure of the random walk starting at X 0 = v. In words, E v C is the expected time taken for the random walk starting at v to visit every vertex of the graph. Over the last decade or so, m... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||