加载中…
We propose the following conjecture extending Dirac’s theorem: if is a graph with vertices and minimum degree , then in every orientation of there is a Hamilton cycle with at least edges oriented in the same direction. We prove an approximate version of this conjecture, showing that minimum degree guarantees a Hamilton cycle with at least edges oriented in the same direction. We also study the analogous problem for random graphs, showing that if the edge probability is above the Hamiltonicity threshold, then, with high probability, in every orientation of there is a Hamilton cycle with edges oriented in the same direction.

生成讲解博客的中文版本

生成AI智能校验的中文版本