×

zbMATH — the first resource for mathematics

On matchings and Hamiltonian cycles in random graphs. (English) Zbl 0592.05052
Random graphs ’83, Lect. 1st Semin., Poznań/Pol. 1983, Ann. Discrete Math. 28, 23-46 (1985).
[For the entire collection see Zbl 0582.00006.]
A graph is chosen randomly from the set of graphs of order n and size \(m=m(n)\) having no isolated vertices. The limiting probability of a graph with a perfect matching is obtained. It is also shown that if a graph of order n is constructed by randomly adding edges one at a time then, almost surely, as soon as the minimum degree is equal to any fixed positive integer k, there are \(\lfloor k/2\rfloor\) disjoint hamiltonian cycles and, if k is odd, a disjoint perfect matching.
Reviewer: O.Frank

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs