Home » Subject » Graph Theory » Directed Graphs » Tournaments

Edge-disjoint Hamilton cycles in highly strongly connected tournaments.

Importance: Medium ✭✭
Author(s): Thomassen, Carsten
Subject: Graph Theory
» Directed Graphs
» » Tournaments
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 8th, 2013
Conjecture   For every $ k\geq 2 $, there is an integer $ f(k) $ so that every strongly $ f(k) $-connected tournament has $ k $ edge-disjoint Hamilton cycles.

Kelly made the following conjecture which replaces the assumption of high connectivity by regularity.

Conjecture   Every regular tournament of order $ n $ can be decomposed into $ (n-1)/2 $ Hamilton directed cycles.

Kelly's conjecture has been proved for tournaments of sufficiently large order by Kühn and Osthus [KO].

Related problems

Decomposing an even tournament in directed paths.

Bibliography

[KO] Daniela Kühn and Deryk Osthus, Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments, Advances in Mathematics 237 (2013), 62-146.

*[T] C. Thomassen, Edge-disjoint Hamiltonian paths and cycles in tournaments, Proc. London Math. Soc. 45 (1982), 151-168.


* indicates original appearance(s) of problem.
add new comment