Cover time of a random graph with a degree sequence II: Allowing vertices of degree two1. Issue 4 (6th February 2015)

• Record Type: Journal Article
• Authors: Cooper, Colin; Frieze, Alan; Lubetzky, Eyal
• Is Part Of: Random structures & algorithms. Volume 45:Issue 4(2014)
• Page Start: 627
• Page End: 674
• Publication Date: 2015-02-06
• Subjects: random graphs -- emerging giant -- cover time; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20573
• Languages: English
• ISSNs: 1042-9832

Abstract

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 = ( d i ) i = 1 n . 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 ond, 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 ) . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 627–674, 2014