Cover time of a random graph with a degree sequence II: Allowing vertices of degree two1. Issue 4 (4th October 2014) - Cooper, Colin; Frieze, Alan; Lubetzky, Eyal
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh21kb0dnk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=(di)i=1n</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh21kb0dp4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, p)</alternatives>. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 627–674, 2014