Premium
Almost all cubic graphs are Hamiltonian
Author(s) -
Robinson R. W.,
Wormald N. C.
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030202
Subject(s) - mathematics , hamiltonian (control theory) , cubic graph , combinatorics , cubic function , hamiltonian path , pancyclic graph , limit (mathematics) , discrete mathematics , graph , mathematical analysis , chordal graph , 1 planar graph , line graph , mathematical optimization , voltage graph
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.