Almost all cubic graphs are Hamiltonian

R. W. Robinson, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

113 Citations (Scopus)

Abstract

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
Volume3
Issue number2
DOIs
Publication statusPublished - 1992
Externally publishedYes

Cite this