The reviewed record of science sign in
Pith

arxiv: 2203.07148 · v2 · pith:JOFAUNLE · submitted 2022-03-14 · math.CO

Oriented discrepancy of Hamilton cycles

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:JOFAUNLErecord.jsonopen to challenge →

classification math.CO
keywords hamiltonorientedcycledirectionedgessameconjecturedegree
0
0 comments X
read the original abstract

We propose the following conjecture extending Dirac's theorem: if $G$ is a graph with $n\ge 3$ vertices and minimum degree $\delta(G)\ge n/2$, then in every orientation of $G$ there is a Hamilton cycle with at least $\delta(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.