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

Cooper Colin | Zendy; Frieze Alan | Zendy; Lubetzky Eyal | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research