Cover Time of a Random Graph With a Degree Sequence II: Allowing Vertices of Degree Two

被引：4

作者：

Cooper, Colin ^{[1
]}

Frieze, Alan ^{[2
]}

Lubetzky, Eyal ^{[3
]}

机构：

[1] Univ London, Kings Coll, Dept Comp Sci, London WC2R 2LS, England

[2] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[3] Microsoft Res, Redmond, WA 98052 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 2014年 / 45卷 / 04期

关键词：

random graphs; emerging giant; cover time; RANDOM-WALKS; GIANT COMPONENT;

D O I：

10.1002/rsa.20573

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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. 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). (c) 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 627-674, 2014

引用

页码：627 / 674

页数：48

共 25 条

[21] A BERRY-ESSEEN BOUND WITH APPLICATIONS TO VERTEX DEGREE COUNTS IN THE ERDOS-RENYI RANDOM GRAPH
Goldstein, Larry
ANNALS OF APPLIED PROBABILITY, 2013, 23 (02) : 617 - 636
[22] Degree-based goodness-of-fit tests for heterogeneous random graph models: Independent and exchangeable cases
Ouadah, Sarah
Robin, Stephane
Latouche, Pierre
SCANDINAVIAN JOURNAL OF STATISTICS, 2020, 47 (01) : 156 - 181
[23] Random Walks Which Prefer Unvisited Edges: Exploring High Girth Even Degree Expanders in Linear Time
Berenbrink, Petra
Cooper, Colin
Friedetzky, Tom
RANDOM STRUCTURES & ALGORITHMS, 2015, 46 (01) : 36 - 54
[24] An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
Frieze, Alan
Haber, Simi
RANDOM STRUCTURES & ALGORITHMS, 2015, 47 (01) : 73 - 98
[25] The Global Mean First-Passage Time for Degree-Dependent Random Walks in a Class of Fractal Scale-Free Trees
Gao, Long
Peng, Junhao
Tang, Chunming
Xu, Qiuxia
Chen, Qi
FRACTAL AND FRACTIONAL, 2024, 8 (11)

← 1 2 3 →