Random graph's Hamiltonicity is strongly tied to its minimum degree (Q2290359)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Random graph's Hamiltonicity is strongly tied to its minimum degree |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8639493584632874
0 references
0.856846272945404
0 references
