Paper Info
Title
Cover time of a random graph with a degree sequence II: Allowing vertices of degree two
Abstract
AbstractWe 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=dii=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 Gn,p. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 627-674, 2014
Year
DOI
Venue
2014
10.1002/rsa.20573
Periodicals
Keywords
Field
DocType
random graphs,emerging giant,cover time
Random regular graph,Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Random walk,Giant component,Degree (graph theory),Corollary,Mathematics,Frieze
Journal
Volume
Issue
ISSN
45
4
1042-9832
Citations 
PageRank 
References 
0
0.34
14
Authors
3
Name
Order
Citations
PageRank
Colin Cooper185791.88
Alan M. Frieze24837787.00
Eyal Lubetzky335528.87