Document Zbl 0494.05056

Matchings and k-factors in a random graph. (English) Zbl 0494.05056

Stud. Sci. Math. Hung. 17, 335-340 (1982).

A random graph on n vertices has independent edge-occurrences with a common probability p that depends on n. Conditions are given for the almost sure existence of k-factors as \(n\to \infty\).

Reviewer: O.Frank

Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0494.05056

MSC:

05C99	Graph theory
60C05	Combinatorial probability
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

almost sure property; random graph; complete graph; disjoint matchings; k-factor

Cite Review PDF