Almost all regular graphs are hamiltonian

R. W. Robinson, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

118 Citations (Scopus)

Abstract

In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r‐regular graphs are hamiltonian for any fixed r ⩾ 3, by an analysis of the distribution of 1‐factors in random regular graphs. Moreover, almost all such graphs are r‐edge‐colorable if they have an even number of vertices. Similarly, almost all r‐regular bipartite graphs are hamiltonian and r‐edge‐colorable for fixed r ⩾ 3. © 1994 John Wiley & Sons, Inc.

Original languageEnglish
Pages (from-to)363-374
Number of pages12
JournalRandom Structures & Algorithms
Volume5
Issue number2
DOIs
Publication statusPublished - 1994
Externally publishedYes

Cite this