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 条
  • [41] Maximal sets of hamilton cycles in complete multipartite graphs
    Daven, M
    MacDougall, JA
    Rodger, CA
    JOURNAL OF GRAPH THEORY, 2003, 43 (01) : 49 - 66
  • [42] Hamilton cycles in line graphs of 3-hypergraphs
    Kaiser, Tomas
    Vrana, Petr
    DISCRETE MATHEMATICS, 2022, 345 (10)
  • [43] Hamilton cycles in primitive graphs of order 2rs
    Du, Shaofei
    Tian, Yao
    Yu, Hao
    ARS MATHEMATICA CONTEMPORANEA, 2023, 23 (03)
  • [44] A Note on Edge-Disjoint Hamilton Cycles in Line Graphs
    Hao Li
    Weihua He
    Weihua Yang
    Yandong Bai
    Graphs and Combinatorics, 2016, 32 : 741 - 744
  • [45] Maximal sets of Hamilton cycles in complete multipartite graphs IV
    Tidwell, David M.
    Rodger, C. A.
    DISCRETE MATHEMATICS, 2022, 345 (08)
  • [46] A Note on Edge-Disjoint Hamilton Cycles in Line Graphs
    Li, Hao
    He, Weihua
    Yang, Weihua
    Bai, Yandong
    GRAPHS AND COMBINATORICS, 2016, 32 (02) : 741 - 744
  • [47] Multiple Hamilton cycles in bipartite cubic graphs: An algebraic method
    Alahmadi, Adel N.
    Glynn, David G.
    FINITE FIELDS AND THEIR APPLICATIONS, 2017, 44 : 18 - 21
  • [48] Cycles in k-traceable oriented graphs
    van Aardt, Susan A.
    Dunbar, Jean E.
    Frick, Marietjie
    Nielsen, Morten H.
    DISCRETE MATHEMATICS, 2011, 311 (18-19) : 2085 - 2094
  • [49] Edge Disjoint Hamilton Cycles in Intersection Graphs of Bases of Matroids
    Zhang, Ying-hao
    Yu, Qinglin Roger
    Liu, Gui-zhen
    UTILITAS MATHEMATICA, 2013, 90 : 327 - 334
  • [50] The Diameters of Some Transition Graphs Constructed from Hamilton Cycles
    Mariko Hagita
    Yoshiaki Oda
    Katsuhiro Ota
    Graphs and Combinatorics, 2002, 18 : 105 - 117