Hamiltonicity of random graphs produced by 2-processes
Andras Telcs, Nicholas Wormald, Sanming Zhou
RANDOM STRUCTURES & ALGORITHMS | JOHN WILEY & SONS INC | Published : 2007
Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2-regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process. © 2006 Wiley Periodicals, Inc.