Oriented discrepancy of Hamilton cycles

DOI10.1002/JGT.22947MaRDI QIDQ6047963zbMATH OpenFDO

Authors Lior Gishboliner, Michael Krivelevich, Peleg Michaeli

Publication date 10 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2203.07148

zbMATH Keywords

Dirac's theoremHamilton cycleoriented discrepancy

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: We propose the following conjecture extending Dirac's theorem: if $G$ is a graph with $nge3$ vertices and minimum degree $delta(G)gen/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 $GsimG(n,p)$ there is a Hamilton cycle with $(1-o(1))n$ edges oriented in the same direction.

Recommendations

• Hamilton Cycles in Oriented Graphs
• scientific article; zbMATH DE number 1047732
• Oriented hamilton cycles in digraphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• Arbitrary orientations of Hamilton cycles in digraphs
• scientific article; zbMATH DE number 426372
• Orientations of Hamiltonian cycles in bipartite digraphs
• Orientations of hamiltonian cycles in large digraphs
• Hamiltonian numbers in oriented graphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs

Cites work

• A discrepancy version of the Hajnal-Szemerédi theorem
• A note on color-bias Hamilton cycles in dense graphs
• A survey on Hamilton cycles in directed graphs
• Advances on the Hamiltonian problem -- a survey
• Color‐biased Hamilton cycles in random graphs
• Cycle lengths in expanding graphs
• Discrepancies of spanning trees and Hamilton cycles
• Geometric discrepancy. An illustrated guide
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3659602 (Why is no real title available?)
• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• scientific article; zbMATH DE number 3215865 (Why is no real title available?)
• Long paths and Hamiltonicity in random graphs
• On a theorem of Rademacher-Turán
• On the discrepancies of graphs
• Powers of Hamilton cycles of high discrepancy are unavoidable
• Recent advances on the Hamiltonian problem: survey III
• Robustness of graph properties
• Some Theorems on Abstract Graphs
• The size Ramsey number of a directed path
• Updating the hamiltonian problem—A survey

Cited in

(5)

• Powers of Hamilton cycles of high discrepancy are unavoidable
• An oriented discrepancy version of Dirac's theorem
• Tight Hamilton cycles with high discrepancy
• Notes on discrepancy and anti-discrepancy in oriented graphs
• Discrepancies of subtrees

This page was built for publication: Oriented discrepancy of Hamilton cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047963)