Random regular graphs of high degree

Michael Krivelevich; Benny Sudakov; Van H. Vu; Nicholas C. Wormald

doi:10.1002/rsa.1013

Random regular graphs of high degree

Michael Krivelevich
, Benny Sudakov
, Van H. Vu
, Nicholas C. Wormald

Research output: Contribution to journal › Article › Research › peer-review

72 Citations (Scopus)

Abstract

Random d-regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d-regular graph when d = d(n) grows more quickly than √n. These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others.

Original language	English
Pages (from-to)	346-363
Number of pages	18
Journal	Random Structures and Algorithms
Volume	18
Issue number	4
DOIs	https://doi.org/10.1002/rsa.1013
Publication status	Published - Jul 2001
Externally published	Yes

Access to Document

10.1002/rsa.1013

Cite this

@article{b724d434bf9340f285154492be45f24b,

title = "Random regular graphs of high degree",

abstract = "Random d-regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d-regular graph when d = d(n) grows more quickly than √n. These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others.",

author = "Michael Krivelevich and Benny Sudakov and Vu, \{Van H.\} and Wormald, \{Nicholas C.\}",

year = "2001",

month = jul,

doi = "10.1002/rsa.1013",

language = "English",

volume = "18",

pages = "346--363",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley \& Sons",

number = "4",

}

TY - JOUR

T1 - Random regular graphs of high degree

AU - Krivelevich, Michael

AU - Sudakov, Benny

AU - Vu, Van H.

AU - Wormald, Nicholas C.

PY - 2001/7

Y1 - 2001/7

N2 - Random d-regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d-regular graph when d = d(n) grows more quickly than √n. These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others.

AB - Random d-regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d-regular graph when d = d(n) grows more quickly than √n. These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others.

UR - https://www.scopus.com/pages/publications/0035609582

U2 - 10.1002/rsa.1013

DO - 10.1002/rsa.1013

M3 - Article

AN - SCOPUS:0035609582

SN - 1042-9832

VL - 18

SP - 346

EP - 363

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

Random regular graphs of high degree

Abstract

Access to Document

Other files and links

Cite this