Random Graph Processes with Degree Restrictions

A. Ruciński; N. C. Wormald

doi:10.1017/S0963548300000183

Random Graph Processes with Degree Restrictions

A. Ruciński
, N. C. Wormald

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

71 Citations (Scopus)

Abstract

Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d. We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with [formula omitted] nd / 2[formula omitted] edges.

Original language	English
Pages (from-to)	169-180
Number of pages	12
Journal	Combinatorics, Probability and Computing
Volume	1
Issue number	2
DOIs	https://doi.org/10.1017/S0963548300000183
Publication status	Published - 1992
Externally published	Yes

Access to Document

10.1017/S0963548300000183

Cite this

@article{4ee285ad274642348020387bd1686516,

title = "Random Graph Processes with Degree Restrictions",

abstract = "Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d. We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with [formula omitted] nd / 2[formula omitted] edges.",

author = "A. Ruci{\'n}ski and Wormald, \{N. C.\}",

year = "1992",

doi = "10.1017/S0963548300000183",

language = "English",

volume = "1",

pages = "169--180",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "2",

}

TY - JOUR

T1 - Random Graph Processes with Degree Restrictions

AU - Ruciński, A.

AU - Wormald, N. C.

PY - 1992

Y1 - 1992

N2 - Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d. We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with [formula omitted] nd / 2[formula omitted] edges.

AB - Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d. We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with [formula omitted] nd / 2[formula omitted] edges.

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

U2 - 10.1017/S0963548300000183

DO - 10.1017/S0963548300000183

M3 - Article

AN - SCOPUS:84971757738

SN - 0963-5483

VL - 1

SP - 169

EP - 180

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 2

ER -

Random Graph Processes with Degree Restrictions

Abstract

Access to Document

Other files and links

Cite this