Decomposing <Emphasis Type="Italic">k</Emphasis>-ARc-Strong Tournaments Into Strong Spanning Subdigraphs |
| |
Authors: | Email author" target="_blank">J?rgen?Bang-JensenEmail author Anders?Yeo |
| |
Institution: | (1) Department of Mathematics and Computer Science , University of Southern Denmark, Odense, DK-5230, Denmark;(2) Department of Computer Science, Royal Holloway University of London, Egham Surrey TW20 0EX, United Kingdom |
| |
Abstract: | The so-called Kelly conjecture 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. |
| |
Keywords: | " target="_blank"> Mathematics Subject Classification (2000): 05C20 05C38 05C40 05C70 |
本文献已被 SpringerLink 等数据库收录! |
|