Bang-Jensen, J. and Yeo, A. (2004) Decomposing k-arc-strong tournaments into strong spanning subdigraphs. Combinatorica, 24 (3).
Full text access: Open
The so-called Kelly conjecture1 states that every regular tournament on 2k+1 vertices has a decomposition into k-arc-disjoint hamiltonian cycles. In this paper we formulate a generalization of that conjecture, namely we conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. We prove several results which support the conjecture: If D = (V, A) is a 2-arc-strong semicomplete digraph then it contains 2 arc-disjoint spanning strong subdigraphs except for one digraph on 4 vertices. Every tournament which has a non-trivial cut (both sides containing at least 2 vertices) with precisely k arcs in one direction contains k arc-disjoint spanning strong subdigraphs. In fact this result holds even for semicomplete digraphs with one exception on 4 vertices. Every k-arc-strong tournament with minimum in- and out-degree at least 37k contains k arc-disjoint spanning subdigraphs H 1, H 2, . . . , H k such that each H i is strongly connected. The last result implies that if T is a 74k-arc-strong tournament with speci.ed not necessarily distinct vertices u 1, u 2, . . . , u k , v 1, v 2, . . . , v k then T contains 2k arc-disjoint branchings where is an in-branching rooted at the vertex u i and is an out-branching rooted at the vertex v i , i=1,2, . . . , k. This solves a conjecture of Bang-Jensen and Gutin [3]. We also discuss related problems and conjectures.
This is a Submitted version This version's date is: 7/2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/0b7ea1ba-0f00-e8e5-3387-48a41db3b2af/6/
Deposited by Research Information System (atira) on 03-Jul-2014 in Royal Holloway Research Online.Last modified on 03-Jul-2014