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

DOI10.1002/RSA.20573MaRDI QIDQ5256387zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Colin Cooper, Eyal Lubetzky, Alan 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

cover timeemerging giantrandom graphs

Mathematics Subject Classification ID

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

Abstract: We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $mathbfd=(d_i{)}_{i=1}^n$. In a previous work, the asymptotic cover time was obtained under a number of assumptions on $mathbfd$, the most significant being that $d_{i}geq3$ for all $i$. Here we replace this assumption by $d_{i}geq2$. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of $mathcalG(n,p)$.

Recommendations

• Cover time of a random graph with given degree sequence
• Cover time of a random graph with given degree sequence
• The cover time of the giant component of a random graph
• The cover time of two classes of random graphs
• The Cover Time of Random Digraphs

Cites work

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

Cited in

(8)

• Cover time of a random graph with given degree sequence
• The cover time of the giant component of a random graph
• Cover time of a random graph with given degree sequence
• The degree-wise effect of a second step for a random walk on a graph
• A probabilistic proof of Cooper \& Frieze's ``First Visit Time Lemma
• Analytical results for the distribution of cover times of random walks on random regular graphs
• On the cover time of the emerging giant
• Cover and hitting times of hyperbolic random graphs

This page was built for publication: Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5256387)