language: en

Almost All Regular Graphs are Hamiltonian

R. W. Robinson
Computer Science Department University of Georgia
Athens, GA 30602, U.S.A.
N. C. Wormald
Department of Mathematics University of Melbourne
Parkville, VIC 3052, Australia

Abstract In a previous paper the authors showed that almost all labelled cubic graphs are hamiltonian. In the present paper, 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-colourable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colourable for fixed r 3.

[Research supported by the Australian Research Council]