Premium
Cover time of a random graph with a degree sequence II: Allowing vertices of degree two
Author(s) -
Cooper Colin,
Frieze Alan,
Lubetzky Eyal
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20573
Subject(s) - combinatorics , mathematics , giant component , degree (music) , random graph , cover (algebra) , frieze , corollary , random regular graph , vertex (graph theory) , graph , discrete mathematics , sequence (biology) , edge cover , line graph , 1 planar graph , physics , geography , mechanical engineering , archaeology , biology , acoustics , engineering , genetics
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 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 ) . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 627–674, 2014