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 条
  • [21] K-Factors and Hamilton Cycles in Graphs
    Zhi Guo WANG
    Zhen Jiang ZHAO
    ActaMathematicaSinica(EnglishSeries), 2007, 23 (02) : 309 - 312
  • [22] K-Factors and Hamilton Cycles in Graphs
    Zhi Guo Wang
    Zhen Jiang Zhao
    Acta Mathematica Sinica, English Series, 2007, 23 : 309 - 312
  • [23] Decompositions of complete graphs into triangles and Hamilton cycles
    Bryant, D
    Maenhaut, B
    JOURNAL OF COMBINATORIAL DESIGNS, 2004, 12 (03) : 221 - 232
  • [24] Optimal covers with Hamilton cycles in random graphs
    Hefetz, Dan
    Kuehn, Daniela
    Lapinskas, John
    Osthus, Deryk
    COMBINATORICA, 2014, 34 (05) : 573 - 596
  • [25] HAMILTON CYCLES IN DOUBLE GENERALIZED PETERSEN GRAPHS
    Sakamoto, Yutaro
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) : 117 - 123
  • [26] Finding Hamilton cycles in random intersection graphs
    Rybarczyk, Katarzyna
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2018, 20 (01)
  • [27] Subdivisions of oriented cycles in digraphs with large chromatic number
    Cohen, Nathann
    Havet, Frederic
    Lochet, William
    Nisse, Nicolas
    JOURNAL OF GRAPH THEORY, 2018, 89 (04) : 439 - 456
  • [28] Properties of Hamilton cycles of circuit graphs of matroids
    Fan, Hao
    Liu, Guizhen
    FRONTIERS OF MATHEMATICS IN CHINA, 2013, 8 (04) : 801 - 809
  • [29] K-factors and Hamilton cycles in graphs
    Wang, Zhi Guo
    Zhao, Zhen Jiang
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (02) : 309 - 312
  • [30] Neighborhood Unions and Hamilton Cycles in Bipartite Graphs
    刘一平
    吴正声
    张雪荣
    东北数学, 1996, (01) : 46 - 50