Hamilton cycles in dense regular digraphs and oriented graphs

被引:0
|
作者
Lo, Allan [1 ]
Patel, Viresh [2 ]
Yildiz, Mehmet Akif [3 ]
机构
[1] Univ Birmingham, Sch Math, Birmingham, England
[2] Queen Mary Univ London, Sch Math Sci, London, England
[3] Univ Amsterdam, Korteweg de Vries Inst Wiskunde, Amsterdam, Netherlands
基金
英国工程与自然科学研究理事会;
关键词
Hamilton cycle; Robust expander; Regular; Digraph; Oriented graph; DECOMPOSITIONS; EXPANDERS;
D O I
10.1016/j.jctb.2023.09.004
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that for every epsilon > 0 there exists n(0) = n(0)(epsilon) such that every regular oriented graph on n > n(0) vertices and degree at least (1/4 + epsilon)n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of Kuhn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions.(c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).
引用
收藏
页码:119 / 160
页数:42
相关论文
共 50 条
  • [1] Counting and packing Hamilton cycles in dense graphs and oriented graphs
    Ferber, Asaf
    Krivelevich, Michael
    Sudakov, Benny
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 196 - 220
  • [2] DIRECTED HAMILTON CYCLES IN DIGRAPHS AND MATCHING ALTERNATING HAMILTON CYCLES IN BIPARTITE GRAPHS
    Zhang, Zan-Bo
    Zhang, Xiaoyan
    Wen, Xuelian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) : 274 - 289
  • [3] Hamilton cycles in digraphs of unitary matrices
    Gutin, G.
    Rafiey, A.
    Severini, S.
    Yeo, A.
    DISCRETE MATHEMATICS, 2006, 306 (24) : 3315 - 3320
  • [4] Hamilton cycles in pseudorandom graphs
    Glock, Stefan
    Correia, David Munha
    Sudakov, Benny
    ADVANCES IN MATHEMATICS, 2024, 458
  • [5] Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs
    Ning, Bo
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 221 - 224
  • [6] RAINBOW HAMILTON CYCLES IN RANDOMLY COLORED RANDOMLY PERTURBED DENSE GRAPHS
    Aigner-Horev, Elad
    Hefetz, Dan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (03) : 1569 - 1577
  • [7] Hamilton cycles in sparse robustly expanding digraphs
    Lo, Allan
    Patel, Viresh
    ELECTRONIC JOURNAL OF COMBINATORICS, 2018, 25 (03):
  • [8] A POLYNOMIAL-TIME ALGORITHM TO DETERMINE (ALMOST) HAMILTONICITY OF DENSE REGULAR GRAPHS
    Patel, Viresh
    Stroh, Fabian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (02) : 1363 - 1393
  • [9] Hamilton cycles in random lifts of directed graphs
    Chebolu, Prasad
    Frieze, Alan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (02) : 520 - 540
  • [10] Hamilton cycles in graphs and hypergraphs: an extremal perspective
    Kuhn, Daniela
    Osthus, Deryk
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, : 381 - 406