The cover time of two classes of random graphs

ABSTRACT

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, Lovász 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.

REFERENCES

• 1: D. J. Aldous, On the time taken by random walks on finite groups to visit every state, Z. Wahrscheinlichkeit-stheorie verw. Gebeite 62 (1983) 361--374.
• 2: R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász and C. Rackoff, Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science (1979) 218--223.
• 3: Noga Alon, Tools from higher algebra, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
• 4: A. Barabási and R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509--512.
• 5: B. Bollobás, Random graphs, in Combinatorics, (H.N.V. Temperley, Ed.), London Mathematical Society Lecture Notes Series 52, Cambridge University Press (1981) 80--102.
• 6: B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal on Combinatorics 1 (1980) 311--316.
• 7: B. Bollobás and O. Riordan, The diameter of a scale-free random graph, Combinatorica.
• 8: B. Bollobás and O. Riordan and J. Spencer and G. Tusanády, The degree sequence of a scale-free random graph process,
• 9: J. Brown and R. Churchill, Complex Variables and Applications, (Sixth Edition) McGraw-Hill (1996).
• 10: Colin Cooper , Alan Frieze, The cover time of sparse random graphs., Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Uriel Feige, A tight upper bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.1, p.51-54, Jan. 1995 [doi>10.1002/rsa.3240060106]
• 12: Uriel Feige, A tight lower bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.4, p.433-438, July 1995 [doi>10.1002/rsa.3240060406]
• 13: W. Feller, An Introduction to Probability Theory, Volume I, (Second edition) Wiley (1960).
• 14: J. Friedman, A proof of Alon's second eignevalue conjecture, to appear.
• 15: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 16: Johan Jonasson, On the Cover Time for Random Walks on Random Graphs, Combinatorics, Probability and Computing, v.7 n.3, p.265-279, September 1998 [doi>10.1017/S0963548398003538]
• 17: L. Lovász, Combinatorial Problems and Exercises, North Holland, 2nd Edition 1993.
• 18: Milena Mihail , Christos Papadimitriou , Amin Saberi, On Certain Connectivity Properties of the Internet Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.28, October 11-14, 2003
• 19: Herbert S. Wilf, Generating functionology, Academic Press Professional, Inc., San Diego, CA, 1990