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 条
  • [31] Hamilton cycles in claw-heavy graphs
    Chen, Bing
    Zhang, Shenggui
    Qiao, Shengning
    DISCRETE MATHEMATICS, 2009, 309 (08) : 2015 - 2019
  • [32] Properties of Hamilton cycles of circuit graphs of matroids
    Hao Fan
    Guizhen Liu
    Frontiers of Mathematics in China, 2013, 8 : 801 - 809
  • [33] Hamilton cycles in a family of graphs which includes the generalized Petersen graphs
    Dean, Matthew
    ARS COMBINATORIA, 2012, 103 : 205 - 224
  • [34] Counting Hamilton cycles in sparse random directed graphs
    Ferber, Asaf
    Kwan, Matthew
    Sudakov, Benny
    RANDOM STRUCTURES & ALGORITHMS, 2018, 53 (04) : 592 - 603
  • [35] Hamilton Cycles in Implicit 2-Heavy Graphs
    Junqing Cai
    Hao Li
    Graphs and Combinatorics, 2016, 32 : 1329 - 1337
  • [36] OPTIMAL PACKINGS OF HAMILTON CYCLES IN SPARSE RANDOM GRAPHS
    Krivelevich, Michael
    Samotij, Wojciech
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 964 - 982
  • [37] Hamilton Cycles in Implicit 2-Heavy Graphs
    Cai, Junqing
    Li, Hao
    GRAPHS AND COMBINATORICS, 2016, 32 (04) : 1329 - 1337
  • [38] Edge-disjoint Hamilton Cycles in Random Graphs
    Knox, Fiachra
    Kuehn, Daniela
    Osthus, Deryk
    RANDOM STRUCTURES & ALGORITHMS, 2015, 46 (03) : 397 - 445
  • [39] Calculating the number of Hamilton cycles in layered polyhedral graphs
    Wirz, Lukas N.
    Schwerdtfeger, Peter
    Avery, James
    COMPUTATIONAL AND MATHEMATICAL METHODS, 2021, 3 (04)
  • [40] Hamilton cycles in almost distance-hereditary graphs
    Chen, Bing
    Ning, Bo
    OPEN MATHEMATICS, 2016, 14 : 19 - 28