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 条
  • [1] Packing, counting and covering Hamilton cycles in random directed graphs
    Ferber, Asaf
    Kronenberg, Gal
    Long, Eoin
    ISRAEL JOURNAL OF MATHEMATICS, 2017, 220 (01) : 57 - 87
  • [2] DIRECTED HAMILTON CYCLES IN DIGRAPHS AND MATCHING ALTERNATING HAMILTON CYCLES IN BIPARTITE GRAPHS
    Zhang, Zan-Bo
    Zhang, Xiaoyan
    Wen, Xuelian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) : 274 - 289
  • [3] Hamilton cycles in random lifts of directed graphs
    Chebolu, Prasad
    Frieze, Alan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (02) : 520 - 540
  • [4] Hamilton cycles in pseudorandom graphs
    Glock, Stefan
    Correia, David Munha
    Sudakov, Benny
    ADVANCES IN MATHEMATICS, 2024, 458
  • [5] Counting Hamilton cycles in sparse random directed graphs
    Ferber, Asaf
    Kwan, Matthew
    Sudakov, Benny
    RANDOM STRUCTURES & ALGORITHMS, 2018, 53 (04) : 592 - 603
  • [6] COMPATIBLE HAMILTON CYCLES IN DIRAC GRAPHS
    Krivelevich, Michael
    Lee, Choongbum
    Sudakov, Benny
    COMBINATORICA, 2017, 37 (04) : 697 - 732
  • [7] HAMILTON CYCLES IN BIDIRECTED COMPLETE GRAPHS
    Busch, Arthur
    Mutar, Mohammed A.
    Slilaty, Daniel
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2022, 17 (02) : 137 - 149
  • [8] Hamilton cycles in graphs and hypergraphs: an extremal perspective
    Kuhn, Daniela
    Osthus, Deryk
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, : 381 - 406
  • [9] Hamilton cycles in (2, odd, 3)-Cayley graphs
    Glover, Henry H.
    Kutnar, Klavdija
    Malnic, Aleksander
    Marusic, Dragan
    PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 2012, 104 : 1171 - 1197
  • [10] POWERS OF HAMILTON CYCLES IN PSEUDORANDOM GRAPHS
    Allen, Peter
    Bottcher, Julia
    Han, Hiep
    Kohayakawa, Yoshiharu
    Person, Yury
    COMBINATORICA, 2017, 37 (04) : 573 - 616
12345