Search

We propose the following extension of Dirac's theorem: if G $G$ is a graph with n≥3 $n\ge 3$ vertices and minimum degree δ(G)≥n∕2 $\delta (G)\ge n\unicode{x02215}2$, then in every orientation of G $G$ there is a Hamilton cycle with at least δ(G) $\delta (G)$ edges oriented in the same direction. We prove an approximate version of this conjecture, showing that minimum degree n+8k2 $\frac{n+8k}{2}$ guarantees a Hamilton cycle with at least (n+k)∕2 $(n+k)\unicode{x02215}2$ edges oriented in the same direction. We also study the analogous problem for random graphs, showing that if the edge probability p=p(n) $p=p(n)$ is above the Hamiltonicity threshold, then, with high probability, in every orientation of G~G(n,p) $G\unicode{x0007E}G(n,p)$ there is a Hamilton cycle with (1−o(1))n $(1-o(1))n$ edges oriented in the same direction. [ABSTRACT FROM AUTHOR]