Getting a directed Hamilton cycle two times faster Academic Article uri icon


  • Abstract Consider the random graph process where we start with an empty graph on n vertices and, at time t, are given an edge et chosen uniformly at random among the edges which have not appeared so far. A classical result in random graph theory asserts that whp the graph becomes Hamiltonian at time (1/2+ o (1)) n log n. On the contrary, if all the edges were directed randomly, then the graph would have a directed Hamilton cycle whp only at time (1+ o (1)) n log n. In this paper we further study the directed case, and ask whether it …

publication date

  • September 1, 2012