Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
复制标题
托马森关于高度关联锦标赛中汉密尔顿循环的猜想的证明
DOI：
10.1112/plms/pdu019
复制
发表时间：
2014
影响因子：
1.8
通讯作者：
Kühn D
中科院分区：
文献类型：
--
作者：
Kühn D
Thomassen 在 1982 年提出的一个猜想指出，对于每一个强连接的锦标赛，都存在边不相交的汉密尔顿循环。卡米恩的一个经典定理，即每个强关联锦标赛都包含一个汉密尔顿循环，暗示了这一点。到目前为止，甚至连它的存在也是公开的。在本文中，我们通过证明托马森的猜想。这最好达到对数因子。作为一种工具，我们表明每个强关联锦标赛都是相关的（这改善了之前的指数界限）。后者的证明基于 Ajtai、Komlós 和 Szemerédi 在渐近最优排序网络上的基本结果。
A conjecture of Thomassen from 1982 states that, for everythere is anso that every strongly-connected tournament containsedge-disjoint Hamilton cycles. A classical theorem of Camion, that every strongly connected tournament contains a Hamilton cycle, implies that. So far, even the existence ofwas open. In this paper, we prove Thomassen's conjecture by showing that. This is best possible up to the logarithmic factor. As a tool, we show that every strongly-connected tournament is-linked (which improves a previous exponential bound). The proof of the latter is based on a fundamental result of Ajtai, Komlós and Szemerédi on asymptotically optimal sorting networks.
登录
查看更多内容
关于半完备有向图的2-联动问题
DOI：
10.1016/s0167-5060(08)70447-3
发表时间：
1988
期刊：
Annals of discrete mathematics
影响因子：
--
作者：
J. Bang
通讯作者：
J. Bang
关于类似锦标赛有向图中的连通性、路径、树和循环的问题和猜想
影响因子：
0.8
作者：
J. Bang
通讯作者：
J. Bang
半完备有向图2路径问题的多项式算法
影响因子：
0.8
作者：
J. Bang;C. Thomassen
通讯作者：
C. Thomassen
高最小次数图中哈密顿循环的最优堆积
DOI：
10.1017/s0963548312000569
发表时间：
2012
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
KÜHN D
通讯作者：
KÜHN D
局部半完全有向图和准及物有向图中的联系
影响因子：
0.8
作者：
J. Bang
通讯作者：
J. Bang