Cover time of a random graph with given degree sequence

DOI10.1016/j.disc.2012.07.006zbMath1252.05207OpenAlexW3022880991WikidataQ57401437 ScholiaQ57401437MaRDI QIDQ456654

Colin Cooper, Alan M. Frieze, Mohammed Amin Abdullah

Publication date: 16 October 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.07.006

zbMATH Keywords

random graphsdegree sequencerandom walks on graphscover time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Random walks on graphs (05C81)

Related Items

Analytical results for the distribution of cover times of random walks on random regular graphs, Voter models on subcritical scale‐free random graphs, A probabilistic proof of Cooper and Frieze's "First Visit Time Lemma", Stationary distribution and cover time of sparse directed configuration models, Global majority consensus by local majority polling on graphs of a given degree sequence, Potential induced random teleportation on finite graphs, Cutoff for random walk on dynamical Erdős-Rényi graph, Recent results of quantum ergodicity on graphs and further investigation, Cover time of a random graph with a degree sequence II: Allowing vertices of degree two, Viral processes by random walks on random regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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})\)
• The cover time of the giant component of a random graph
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• 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