|
|||||
|
|
Spanning 2-strong tournaments in 3-strong semicomplete digraphs |
|
| Authors: | Jø rgen Bang-Jensen,Tibor Jordá n |
| Affiliation: | a Department of Mathematics and Computer Science, University of Southern Denmark, DK-5230, Odense, Denmark b Department of Operations Research, Eötvös University, Pázmány Péter sétány 1/C, 1117 Budapest, Hungary |
| Abstract: | We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph  on 2k vertices contains a spanning k-strong tournament. |
| Keywords: | Connectivity of digraphs Semicomplete digraph Tournament |
| 本文献已被 ScienceDirect 等数据库收录！ | |