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

Colin Cooper; Alan Frieze; Eyal Lubetzky

doi:10.1002/rsa.20573

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

Colin Cooper, Alan Frieze, Eyal Lubetzky

Mathematics

Research output: Contribution to journal › Article › peer-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 d_i ≥ 3 for all i. Here we replace this assumption by d_i ≥ 2. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of G(n,p).

Original language	English (US)
Pages (from-to)	627-674
Number of pages	48
Journal	Random Structures and Algorithms
Volume	45
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20573
State	Published - Dec 1 2014

Keywords

Cover time
Emerging giant
Random graphs

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.20573

Cite this

@article{752d2ac3d9d142f2a0659c666a61752d,

title = "Cover time of a random graph with a degree sequence II: Allowing vertices of degree two",

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).",

keywords = "Cover time, Emerging giant, Random graphs",

author = "Colin Cooper and Alan Frieze and Eyal Lubetzky",

note = "Publisher Copyright: {\textcopyright} 2014 Wiley Periodicals, Inc.",

year = "2014",

month = dec,

day = "1",

doi = "10.1002/rsa.20573",

language = "English (US)",

volume = "45",

pages = "627--674",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - Cover time of a random graph with a degree sequence II

T2 - Allowing vertices of degree two

AU - Cooper, Colin

AU - Frieze, Alan

AU - Lubetzky, Eyal

PY - 2014/12/1

Y1 - 2014/12/1

N2 - 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).

AB - 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).

KW - Cover time

KW - Emerging giant

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=84961383352&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961383352&partnerID=8YFLogxK

U2 - 10.1002/rsa.20573

DO - 10.1002/rsa.20573

M3 - Article

AN - SCOPUS:84961383352

SN - 1042-9832

VL - 45

SP - 627

EP - 674

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this