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

preprint2014arXivOpen access

Abstract

We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set [n][n] and degree sequence d=(di)i=1n\mathbf{d}=(d_i)_{i=1}^n. In a previous work, the asymptotic cover time was obtained under a number of assumptions on d\mathbf{d}, the most significant being that di≥3d_i\geq 3 for all ii. Here we replace this assumption by di≥2d_i\geq 2. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of G(n,p)\mathcal{G}(n,p).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.