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

Colin Cooper, Alan Frieze, Eyal Lubetzky

Research output: Contribution to journalArticlepeer-review

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 d=(di)i=1n. In a previous work (Abdullah, Cooper, and Frieze, Discrete Math 312 (2012), 3146-3163), the asymptotic cover time was obtained under a number of assumptions on d, the most significant being that di ≥ 3 for all i. Here we replace this assumption by di ≥ 2. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of G(n,p).

Original languageEnglish (US)
Pages (from-to)627-674
Number of pages48
JournalRandom Structures and Algorithms
Volume45
Issue number4
DOIs
StatePublished - Dec 1 2014

Keywords

  • Cover time
  • Emerging giant
  • Random graphs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Cover time of a random graph with a degree sequence II: Allowing vertices of degree two'. Together they form a unique fingerprint.

Cite this