On the Existence of Hamilton Cycles with a Periodic Pattern in a Random Digraph

  • Alan Frieze
  • Xavier Pérez-Giménez
  • Paweł Prałat


We consider Hamilton cycles in the random digraph $D_{n,m}$ where the orientation of edges follows a pattern other than the trivial orientation in which the edges are oriented in the same direction as we traverse the cycle. We show that if the orientation forms a periodic pattern, other than the trivial pattern, then approximately half the usual $n\log n$ edges are needed to guarantee the existence of such Hamilton cycles a.a.s.

Article Number