Random graph's Hamiltonicity is strongly tied to its minimum degree (Q2290359)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Random graph's Hamiltonicity is strongly tied to its minimum degree |
scientific article |
Statements
Random graph's Hamiltonicity is strongly tied to its minimum degree (English)
0 references
27 January 2020
0 references
Summary: We show that the probability that a random graph \(G\sim G(n,p)\) contains no Hamilton cycle is \((1+o(1))Pr(\delta (G) < 2)\) for all values of \(p = p(n)\). We also prove an analogous result for perfect matchings.
0 references
Hamilton cycle
0 references
perfect matching
0 references
