Random regular graphs of high degree

Authors
Krivelevich, M Sudakov, B Vu, VH Wormald, NC
Citation
M. Krivelevich et al., Random regular graphs of high degree, RAND STR AL, 18(4), 2001, pp. 346-363
Citations number
33
Categorie Soggetti
Mathematics
Journal title
RANDOM STRUCTURES & ALGORITHMS
ISSN journal
10429832 → ACNP
Volume
18
Issue
4
Year of publication
2001
Pages
346 - 363
Database
ISI
SICI code
1042-9832(200107)18:4<346:RRGOHD>2.0.ZU;2-R
Abstract
Random d-regular graphs have been well studied when tl is fixed and the num ber of vertices goes to infinity. We obtain results on many of the properti es of a random d-regular graph when d = d(n) grows more quickly than rootn. These properties include connectivity, hamiltonicity, independent set size , chromatic number, choice number, and the size of the second eigenvalue, a mong others. (C) 2001 John Wiley & Sons, Inc.