Hamilton cycles in a semi-random graph model

Abstract: We show that with high probability we can build a Hamilton cycle after at most

1.85 n

rounds in a particular semi-random model. In this model, in one round, we are given a {uniform random}

v i n [n]

and then we can add an {arbitrary} edge

v, w

. Our result improves on

2.016 n

in a recent paper of Gao, MacRury, and Pralat.

This page was built for publication: Hamilton cycles in a semi-random graph model