A survey on Hamilton cycles in directed graphs

被引：44
|
作者：
Kuehn, Daniela [1 ]
Osthus, Deryk [1 ]
机构：
[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2012年 / 33卷 / 05期
关键词：
SUFFICIENT CONDITIONS; PATHS; DIGRAPH; TOURNAMENTS; CONJECTURE; CIRCUITS; NUMBER; PROOF;
D O I：
10.1016/j.ejc.2011.09.030
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We survey some recent results on long-standing conjectures regarding Hamilton cycles in directed graphs, oriented graphs and tournaments. We also combine some of these to prove the following approximate result towards Kelly's conjecture on Hamilton decompositions of regular tournaments: the edges of every regular tournament can be covered by a set of Hamilton cycles which are 'almost' edge-disjoint. We also highlight the role that the notion of 'robust expansion' plays in several of the proofs. New and old open problems are discussed. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码：750 / 766
页数：17
相关论文
共 50 条
  • [21] Long cycles in subgraphs of (pseudo)random directed graphs
    Ben-Eliezer, Ido
    Krivelevich, Michael
    Sudakov, Benny
    JOURNAL OF GRAPH THEORY, 2012, 70 (03) : 284 - 296
  • [22] CRUX AND LONG CYCLES IN GRAPHS
    Haslegrave, John
    Hu, Jie
    Kim, Jaehoon
    Liu, Hong
    Luan, Bingyu
    Wang, Guanghui
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (04) : 2942 - 2958
  • [23] Shortest Non-trivial Cycles in Directed Surface Graphs
    Erickson, Jeff
    COMPUTATIONAL GEOMETRY (SCG 11), 2011, : 236 - 243
  • [24] Counting orientations of random graphs with no directed k-cycles
    Campos, Marcelo
    Collares, Mauricio
    Mota, Guilherme Oliveira
    RANDOM STRUCTURES & ALGORITHMS, 2024, 64 (03) : 676 - 691
  • [25] Hamilton cycles and paths in vertex-transitive graphs-Current directions
    Kutnar, Klavdija
    Marusic, Dragan
    DISCRETE MATHEMATICS, 2009, 309 (17) : 5491 - 5500
  • [26] Hamilton cycles in vertex-transitive graphs of order 6p
    Du, Shaofei
    Zhou, Tianlei
    DISCRETE APPLIED MATHEMATICS, 2025, 368 : 165 - 175
  • [27] Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
    Fox, Kyle
    PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), 2013, : 352 - 364
  • [28] Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults
    Hu, Xiaolan
    Liu, Huiqing
    Pan, Xiang-Feng
    DISCRETE APPLIED MATHEMATICS, 2014, 169 : 152 - 161
  • [29] Alspach's Problem: The Case of Hamilton Cycles and 5-Cycles
    Jordon, Heather
    ELECTRONIC JOURNAL OF COMBINATORICS, 2011, 18 (01)
  • [30] From kernels in directed graphs to fixed points and negative cycles in Boolean networks
    Richard, Adrien
    Ruet, Paul
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (7-8) : 1106 - 1117
12345