Almost all cubic graphs are Hamiltonian

R. W. Robinson, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

94 Citations (Scopus)


In a previous article the authors showed that at least 98.4% of large labelled cubic graphs are hamiltonian. In the present article, this is improved to 100% in the limit by asymptotic analysis of the variance of the number of Hamilton cycles with respect to populations of cubic graphs with fixed numbers of short odd cycles.

Original languageEnglish
Pages (from-to)117-125
Number of pages9
JournalRandom Structures and Algorithms
Issue number2
Publication statusPublished - 1992
Externally publishedYes

Cite this