Hamilton cycles containing randomly selected edges in random regular graphs

• Published in: Random structures & algorithms 2001-09, Vol.19 (2), p.128-147
• Main Authors: Robinson, R.W., Wormald, N.C.
• Format: Article
• Language: English
• ISSN: 1042-9832; 1098-2418
• DOI: 10.1002/rsa.1024

In previous papers the authors showed that almost all d‐regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if $j=o(\sqrt{n}),$ and the limiting probability distribution at the threshold $j=c\sqrt{n}$ is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw‐free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001