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/).
机构:
Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Jianghan Univ, Inst Interdisciplinary Res, Wuhan, Peoples R ChinaUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Li, Hao
He, Weihua
论文数: 0引用数: 0
h-index: 0
机构:
Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Guangdong Univ Technol, Dept Appl Math, Guangzhou, Guangdong, Peoples R ChinaUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
He, Weihua
Yang, Weihua
论文数: 0引用数: 0
h-index: 0
机构:
Taiyuan Univ Technol, Dept Math, Taiyuan, Peoples R ChinaUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Yang, Weihua
Bai, Yandong
论文数: 0引用数: 0
h-index: 0
机构:
Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, FranceUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
机构:
Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Jianghan Univ, Inst Interdisciplinary Res, Wuhan, Peoples R ChinaUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Li, Hao
He, Weihua
论文数: 0引用数: 0
h-index: 0
机构:
Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Guangdong Univ Technol, Dept Appl Math, Guangzhou, Guangdong, Peoples R ChinaUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
He, Weihua
Yang, Weihua
论文数: 0引用数: 0
h-index: 0
机构:
Taiyuan Univ Technol, Dept Math, Taiyuan, Peoples R ChinaUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
Yang, Weihua
Bai, Yandong
论文数: 0引用数: 0
h-index: 0
机构:
Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, FranceUniv Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France