Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

DOI10.1002/rsa.20573zbMath1320.05109arXiv1406.1142WikidataQ57401417 ScholiaQ57401417MaRDI QIDQ5256387

Eyal Lubetzky, Colin Cooper, Alan M. Frieze

Publication date: 22 June 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.1142

zbMATH Keywords

random graphscover timeemerging giant

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C07: Vertex degrees

Related Items

Analytical results for the distribution of cover times of random walks on random regular graphs, On the Cover Time of the Emerging Giant, A probabilistic proof of Cooper and Frieze's "First Visit Time Lemma"

Cites Work

• Stationary distribution and cover time of random walks on random digraphs
• Cover time of a random graph with given degree sequence
• The cover time of the preferential attachment graph
• Covering problems for Brownian motion on spheres
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• An introduction to covering problems for random walks on graphs
• Anatomy of the giant component: the strictly supercritical regime
• The Evolution of the Cover Time
• The cover time of random geometric graphs
• Anatomy of a young giant component in the random graph
• The cover time of sparse random graphs
• The cover time of the giant component of a random graph
• Cycles in a random graph near the critical point
• A Chernoff Bound for Random Walks on Expander Graphs
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• The Cover Time of Random Regular Graphs