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/).
机构:
Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, IsraelTel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
Krivelevich, Michael
Samotij, Wojciech
论文数: 0引用数: 0
h-index: 0
机构:
Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, EnglandTel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
机构:
Qufu Normal Univ, Sch Management, Rizhao 276826, Peoples R ChinaQufu Normal Univ, Sch Management, Rizhao 276826, Peoples R China
Cai, Junqing
Li, Hao
论文数: 0引用数: 0
h-index: 0
机构:
Univ Paris 11, CNRS, UMR 8623, LRI, F-91405 Orsay, France
Jianghan Univ, Inst Interdisciplinary Res, Wuhan 430019, Peoples R ChinaQufu Normal Univ, Sch Management, Rizhao 276826, Peoples R China
机构:
Univ London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, EnglandUniv London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, England
Knox, Fiachra
Kuehn, Daniela
论文数: 0引用数: 0
h-index: 0
机构:
Univ Birmingham, Coll Engn & Phys Sci, Sch Math, Birmingham B15 2TT, W Midlands, EnglandUniv London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, England
Kuehn, Daniela
Osthus, Deryk
论文数: 0引用数: 0
h-index: 0
机构:
Univ Birmingham, Coll Engn & Phys Sci, Sch Math, Birmingham B15 2TT, W Midlands, EnglandUniv London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, England
机构:
Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, IsraelTel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
Krivelevich, Michael
Samotij, Wojciech
论文数: 0引用数: 0
h-index: 0
机构:
Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, EnglandTel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
机构:
Qufu Normal Univ, Sch Management, Rizhao 276826, Peoples R ChinaQufu Normal Univ, Sch Management, Rizhao 276826, Peoples R China
Cai, Junqing
Li, Hao
论文数: 0引用数: 0
h-index: 0
机构:
Univ Paris 11, CNRS, UMR 8623, LRI, F-91405 Orsay, France
Jianghan Univ, Inst Interdisciplinary Res, Wuhan 430019, Peoples R ChinaQufu Normal Univ, Sch Management, Rizhao 276826, Peoples R China
机构:
Univ London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, EnglandUniv London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, England
Knox, Fiachra
Kuehn, Daniela
论文数: 0引用数: 0
h-index: 0
机构:
Univ Birmingham, Coll Engn & Phys Sci, Sch Math, Birmingham B15 2TT, W Midlands, EnglandUniv London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, England
Kuehn, Daniela
Osthus, Deryk
论文数: 0引用数: 0
h-index: 0
机构:
Univ Birmingham, Coll Engn & Phys Sci, Sch Math, Birmingham B15 2TT, W Midlands, EnglandUniv London, Fac Sci & Engn, Sch Math Sci, Queen Mary, London E1 4NS, England