The so-called Kelly conjecture
1 states that every regular tournament on 2
k+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 74
k-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 2
k arc-disjoint branchings
$
F^{ - }_{{u_{1} }} ,F^{ - }_{{u_{2} }} ,...,F^{ - }_{{u_{k} }} ,F^{ + }_{{v_{1} }} ,F^{ + }_{{v_{2} }} ,...,F^{ + }_{{v_{k} }}
$
F^{ - }_{{u_{1} }} ,F^{ - }_{{u_{2} }} ,...,F^{ - }_{{u_{k} }} ,F^{ + }_{{v_{1} }} ,F^{ + }_{{v_{2} }} ,...,F^{ + }_{{v_{k} }}
where
$
F^{ - }_{{u_{i} }}
$
F^{ - }_{{u_{i} }}
is an in-branching rooted at the vertex
u
i
and
$
F^{ + }_{{v_{i} }}
$
F^{ + }_{{v_{i} }}
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.
Mathematics Subject Classification (2000):
05C20 - 05C38 - 05C40 - 05C70