论文标题
汉密尔顿周期的面向差异
Oriented discrepancy of Hamilton cycles
论文作者
论文摘要
我们提出以下猜想扩展了Dirac的定理：如果$ G $是$ n \ ge 3 $顶点和最低度$δ（g）\ ge n/2 $的图表，那么在$ g $的每个方向上，汉密尔顿周期都有至少$δ（g）$ edges in同一方向。我们证明了该猜想的大约版本，表明最低度$ N/2 + O（k）$可以保证汉密尔顿周期至少$（n + k）/2 $边缘以同一方向为导向。我们还研究了随机图的类似问题，表明，如果边缘概率$ p = p = p（n）$高于汉密尔顿性阈值，那么，在$ g \ sim g（n，p）$的每一个方向上，都有一个hamilton循环，$（1-o（1-o（1-o（1））n $ edges n $ edges在同一方向上。
We propose the following conjecture extending Dirac's theorem: if $G$ is a graph with $n\ge 3$ vertices and minimum degree $δ(G)\ge n/2$, then in every orientation of $G$ there is a Hamilton cycle with at least $δ(G)$ edges oriented in the same direction. We prove an approximate version of this conjecture, showing that minimum degree $n/2 + O(k)$ guarantees a Hamilton cycle with at least $(n+k)/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)$ is above the Hamiltonicity threshold, then, with high probability, in every orientation of $G \sim G(n,p)$ there is a Hamilton cycle with $(1-o(1))n$ edges oriented in the same direction.
